✦ LIBER ✦

Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs

✍ Scribed by Pavon Hell; Jing Huang

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 823 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200312

No coin nor oath required. For personal study only.

✦ Synopsis

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 proper circular arc graphs, and to recognize and represent proper interval graphs. As a consequence, we derive and represent proper interval graphs. As a consequence, we derive simple new proofs of a theorem of Ghouila‐Houri and a theorem of Skrien. Our algorithms are conceptually simpler than (and often of comparable efficiency to) the existing algorithms for these problems. © 1995 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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

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

The round-up property of the fractional

The round-up property of the fractional chromatic number for proper circular arc graphs

✍ Niessen, Thomas; Kind, Jaakob 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 2 views

Let G = (V, E) be a graph and let k be a nonnegative integer. A vector c ∈ Z V + is called k-colorable iff there exists a coloring of G with k colors that assigns exactly c(v) colors to vertex v ∈ V . Denote by χ(G) and χ f (G) the chromatic number and fractional chromatic number, respectively. We p