Bhattacharya, Binay; Hell, Pavol; Huang, Jing A linear algorithm for maximum weight cliques in proper circular arc graphs. (English) Zbl 0854.05092 SIAM J. Discrete Math. 9, No. 2, 274-289 (1996). An undirected graph \(G\) is a proper circular arc graph if there is a one-to-one correspondence between the vertex set \(V(G)\) and a family \(\mathcal F\) of \(n\) arcs on a circle such that two vertices are adjacent if and only if the corresponding two circular arcs intersect and \(\mathcal F\) is inclusion-free. The authors present an \(O(n)\) time algorithm to find a maximum weight clique in a proper circular arc graph assuming that the input graph is represented by a sorted simple family of circular arcs. The best previous algorithm for finding such a clique had a time bound of \(O(n^2)\). Using the approach developed in this paper they also give an \(O(n)\) time algorithm for \(q\)-coloring proper circular arc graphs for a fixed \(q\). Such an algorithm was first given by A. Teng and A. Tucker [Discrete Math. 55, 233-243 (1985; Zbl 0567.68043)]. Reviewer: M.Kubale (Gdańsk) Cited in 6 Documents MSC: 05C85 Graph algorithms (graph-theoretic aspects) 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science Keywords:proper circular arc graph; maximum weight clique; circular arcs; algorithm; \(q\)-coloring Citations:Zbl 0567.68043 PDFBibTeX XMLCite \textit{B. Bhattacharya} et al., SIAM J. Discrete Math. 9, No. 2, 274--289 (1996; Zbl 0854.05092) Full Text: DOI