𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs

✍ Scribed by Chang, Maw-Shang

Book ID
118178117
Publisher
Society for Industrial and Applied Mathematics
Year
1998
Tongue
English
Weight
409 KB
Volume
27
Category
Article
ISSN
0097-5397

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 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

Lexicographic orientation and representa
Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
✍ Pavon Hell; Jing Huang πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 823 KB

## Abstract We introduce a simple new technique which allows us to solve several problems that can be formulated as seeking a suitable orientation of a given undirected graph. In particular, we use this technique to recognize and transitively orient comparability graphs, to recognize and represent