✦ LIBER ✦

Efficient algorithms for interval graphs and circular-arc graphs

✍ Scribed by U. I. Gupta; D. T. Lee; J. Y.-T. Leung

Publisher: John Wiley and Sons
Year: 1982
Tongue: English
Weight: 476 KB
Volume: 12
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230120410

No coin nor oath required. For personal study only.

✦ Synopsis

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 intervals are sorted]. For the more general circular‐arc graphs, a maximum independent set and a minimum covering by disjoint completely connected sets or cliques can be found in O(n^2^) time, provided again that a corresponding family of arcs is given.

📜 SIMILAR VOLUMES

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

Interval bigraphs and circular arc graph

Interval bigraphs and circular arc graphs

✍ Pavol Hell; Jing Huang 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 130 KB

## Abstract We prove that the complements of interval bigraphs are precisely those circular arc graphs of clique covering number two, which admit a representation without two arcs covering the whole circle. We give another characterization of interval bigraphs, in terms of a vertex ordering, that w

A relationship between triangulated grap

A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs

✍ Dale J. Skrien 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 319 KB 👁 1 views

## Abstract Given a set __F__ of digraphs, we say a graph __G__ is a __F__‐__graph__ (resp., __F__\*‐__graph__) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs in __F__. It is proved that all the classes of graphs mentioned in

Polynomial time algorithms on circular-a

Polynomial time algorithms on circular-arc overlap graphs

✍ Toshinobu Kashiwabara; Sumio Masuda; Kazuo Nakajima; Toshio Fujisawa 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 417 KB

Maximum independent sets of circular-arc

Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs

✍ Zheng, S. Q. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 421 KB 👁 2 views

We present a simple optimal algorithm for the problem of finding maximum independent sets of circular-arc graphs. Given an intersection model S of a circular-arc graph G , our algorithm computes a maximum independent set of G in O ( n ) space and O ( n ) or O(n log n ) time, depending on whether the

Partial characterizations of circular-ar

Partial characterizations of circular-arc graphs

✍ F. Bonomo; G. Durán; L.N. Grippo; M.D. Safe 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB

## Abstract A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minim