×

A linear algorithm for maximum weight cliques in proper circular arc graphs. (English) Zbl 0854.05092

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)

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 0567.68043
PDFBibTeX XMLCite
Full Text: DOI