๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs

โœ Scribed by Orlin, James B.; Bonuccelli, Maurizio A.; Bovet, Daniel P.

Book ID
118212385
Publisher
Society for Industrial and Applied Mathematics
Year
1981
Weight
634 KB
Volume
2
Category
Article
ISSN
0196-5212

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

An O(qn) algorithm to q-color a proper f
An O(qn) algorithm to q-color a proper family of circular arcs
โœ Austin Teng; Alan Tucker ๐Ÿ“‚ Article ๐Ÿ“… 1985 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 683 KB

A family of arcs on a circle is proper if no arc is properly contained within another. While general minimal arc coloring is NP-complete, Orlin et al. recently obtained on O(n') algorithm for q-coloring a proper family of arcs by modeling proper arc coloring as a shortest path problem in an associat

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

An Oฬƒ(n314)-coloring algorithm for 3-col
An Oฬƒ(n314)-coloring algorithm for 3-colorable graphs
โœ Avrim Blum; David Karger ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 471 KB

We show how the results of Karger, Motwani, and Sudan ( 1994) and Blum ( 1994) can be combined in a natural manner to yield a polynomial-time algorithm for d(n3"4 )-coloring any n-node 3-colorable graph. This improves on the previous best bound of 6(n'14) colors (Karger et al., 1994).