×

zbMATH — the first resource for mathematics

On cliques of Helly circular-arc graphs. (English) Zbl 1341.05196
Liebling, Th. (ed.) et al., The IV Latin-American algorithms, graphs, and optimization symposium, Puerto Varas, Chile, November 25–29, 2007. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 30, 117-122 (2008).
Summary: A circular-arc graph is the intersection graph of a set of arcs on the circle. It is a Helly circular-arc graph if it has a Helly model, where every maximal clique is the set of arcs that traverse some clique point on the circle. A clique model is a Helly model that identifies one clique point for each maximal clique. A Helly circular-arc graph is proper if it has a Helly model where no arc is a subset of another. In this paper, we show that the clique intersection graphs of Helly circular-arc graphs are related to the proper Helly circular-arc graphs. This yields the first polynomial (linear) time recognition algorithm for the clique graphs of Helly circular-arc graphs. Next, we develop an \(O(n)\) time algorithm to obtain a clique model of Helly model, improving the previous \(O(n^{2})\) bound. This gives a linear-time algorithm to find a proper Helly model for the clique graph of a Helly circular-arc graph. As an application, we find a maximum weighted clique of a Helly circular-arc graph in linear time.
For the entire collection see [Zbl 1137.05001].

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alcón, L.; Faria, L.; Figueiredo, C.; Gutiérrez, M., Clique graph recognition is NP-complete, (), 269-277 · Zbl 1167.68403
[2] Brandstädt, A.; Le, V.; Spinrad, J., Graph classes: A survey, (1999), SIAM · Zbl 0919.05001
[3] Durán, G.; Lin, M., Clique graphs of Helly circular-arc graphs, Ars combin., 60, 255-271, (2001) · Zbl 1072.05565
[4] Durán, G.; Lin, M.; Mera, S.; Szwarcfiter, J., Algorithms for clique-independent sets on subclasses of circular-arc graphs, Discrete appl. math., 154, 1783-1790, (2006) · Zbl 1104.05054
[5] Hamelink, R., A partial characterization of clique graphs, J. combin. theory ser. B, 5, 192-197, (1968) · Zbl 0167.22203
[6] Lin, M., and J. Szwarcfiter, Characterizations and recognition of circular-arc graphs and subclasses: a survey, manuscript, 2006 · Zbl 1228.05218
[7] Lin, M., F. Soulignac and J. Szwarcfiter, Proper Helly circular-arc graphs, Proc. of WG 2007 (2007), to appear · Zbl 1141.68539
[8] Roberts, F.; Spencer, J., A characterization of clique graphs, J. combin. theory ser. B, 10, 102-108, (1971) · Zbl 0215.05801
[9] Shih, W.; Hsu, W., An \(O(n \log n + m \log \log n)\) algorithm for finding a maximum weight clique in circular-arc graphs, Inform. process. lett., 31, 129-134, (1989) · Zbl 0677.68056
[10] Spinrad, J., Efficient graph representations, (2003), Amer. Math. Soc. · Zbl 1033.05001
[11] Szwarcfiter, J., A survey on Clique Graphs, in: “Recent Advances in Algorithms and Combinatorics”, Springer, 109-136 · Zbl 1027.05071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.