𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Efficient algorithms for computing the reliability of permutation and interval graphs

✍ Scribed by Hosam M. Aboeifotoh; Charles J. Colbourn

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
782 KB
Volume
20
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Efficient algorithms for interval graphs
Efficient algorithms for interval graphs and circular-arc graphs
✍ U. I. Gupta; D. T. Lee; J. Y.-T. Leung πŸ“‚ Article πŸ“… 1982 πŸ› John Wiley and Sons 🌐 English βš– 476 KB

## Abstract We show that for an interval graph given in the form of a family of intervals, a maximum independent set, a minimum covering by disjoint completely connected sets or cliques, and a maximum clique can all be found in __O__(__n__ log __n__) time [__O__(__n__) time if the endpoints of the

Efficient parallel algorithms for bipart
Efficient parallel algorithms for bipartite permutation graphs
✍ Lin Chen; Yaacov Yesha πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 858 KB

## Abstract In this paper, we further study the properties of bipartite permutation graphs. We give first efficient parallel algorithms for several problems on bipartite permutation graphs. These problems include transforming a bipartite graph into a strongly ordered one if it is also a permutation

Efficient algorithms for centers and med
Efficient algorithms for centers and medians in interval and circular-arc graphs
✍ Sergei Bespamyatnikh; Binay Bhattacharya; Mark Keil; David Kirkpatrick; Michael πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 267 KB

## Abstract The __p__‐center problem is to locate __p__ facilities on a network so as to minimize the largest distance from a demand point to its nearest facility. The __p__‐median problem is to locate __p__ facilities on a network so as to minimize the average distance from a demand point to its c

Efficient and Constructive Algorithms fo
Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
✍ Hans L. Bodlaender; Ton Kloks πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 373 KB

In this paper we give, for all constants k, l, explicit algorithms that, given a graph Ε½ . Gs V,E with a tree-decomposition of G with treewidth at most l, decide Ε½ . whether the treewidth or pathwidth of G is at most k, and, if so, find a Ε½ . tree-decomposition or path-decomposition of G of width at