NC algorithms for circular-arc graphs
[For the entire collection see Zbl 0753.00021.] Circular-arc graphs are an important class of intersection graphs. They have been applied to problems in genetics, traffic control, multidimensional scaling, computer compiler design, characterization of a certain class of lattices, and some other areas. Many sequential algorithms have been designed for circular-arc graphs. The problem of coloring circular-arc graphs has been investigated by \textit{A. Tucker} [SIAM J. Appl. Math. 29, 493-502 (1975; Zbl 0312.05105)], and the problem was later proved to be NP-complete by \textit{M. R. Garey}, \textit{D. S. Johnson}, \textit{G. L. Miller} and \textit{C. H. Papadimitriou} [SIAM J. Algebraic Discrete Methods 1, 216-227 (1980; Zbl 0499.05058)]. \textit{M. A. Bonuccelli} [Discrete Appl. Math. 12, 203-213 (1985; Zbl 0579.05051)] has shown that the domatic number problem for circular-arc graphs is NP- complete. In this paper, we give several parallel algorithms for circular-arc graphs and some subclasses of circular-arc graphs. We begin with the graph recognition problem, which is the first important problem for any class of graphs. It sets the foundation for solving many other problems of that class of graphs. Here we show, for the first time, three subclasses of circular-arc graphs can be recognized in polylogarithmic time with polynomially bounded processors. Specifically, \(\bullet\) a proper circular-arc graph can be recognized in \(O(\log^ 2 n)\) time with \(O(n^ 3)\) processors. \(\bullet\) a \(\Delta\) circular-arc graph can be recognized in \(O(\log^ 2 n)\) time with \(O(n^ 6)\) processors. \(\bullet\) a graph whose augmented adjacency matrix has the circular 1's property can be recognized in \((\log^ 2 n)\) time with \(O(n^ 3)\) processors. A circular-arc representation can also be constructed within the same resource bounds for the latter two classes of graphs. In addition, we give first efficient parallel algorithms for four well-known problems on the circular-arc representation. Specifically, we show \(\bullet\) a maximum independent set can be obtained in \(O(\log n)\) time with \(O(n^ 2)\) processors. \(\bullet\) a minimum dominating set can be obtained in \(O(\log n)\) time with \(O(n^ 2)\) processors. \(\bullet\) a minimum clique cover can be obtained in \(O(n\log n)\) time with \(O(n^ 2)\) processors. \(\bullet\) a maximum clique can be obtained in \(O(\log n)\) time with \(O(n^ 3)\) processors.
- Circular-arc graphs with clique cover number two
- Linear time algorithms on circular-arc graphs
- Efficient parallel recognition of some circular arc graphs. I
- Optimal parallel algorithms on circular-arc graphs
- Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs
- Revisiting Tucker's algorithm to color circular-arc graphs
- Polynomial time algorithms on circular-arc overlap graphs
- scientific article; zbMATH DE number 4215389 (Why is no real title available?)
- O(M\cdot N) Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- Independent Sets in Circular-Arc Graphs
- Parallel algorithms on circular-arc graphs
- Parallel algorithms on circular-arc graphs
- Optimal algorithms for computing articulation points and some related problems on a circular-arc graph
- Efficient parallel recognition of some circular arc graphs. II
- A constant factor approximation algorithm for boxicity of circular arc graphs
This page was built for publication: NC algorithms for circular-arc graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4028894)
