| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429806 | Journal of Algorithms | 2006 | 12 Pages |
Abstract
We present an efficient algorithm for recognizing unit circular-arc (UCA) graphs, based on a characterization theorem for UCA graphs proved by Tucker in the seventies. Given a proper circular-arc (PCA) graph G, the algorithm starts from a PCA model for G, removes all its circle-covering pairs of arcs and determines whether G is a UCA graph. We also give an O(N) time bound for Tucker's 3/2-approximation algorithm for coloring circular-arc graphs with N vertices, when a circular-arc model is given.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
