NC algorithms for circular-arc graphs (Q4028894)

[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.