zbMATH — the first resource for mathematics

Algorithms for clique-independent sets on subclasses of circular-arc graphs. (English) Zbl 1104.05054
Authors’ abstract: A circular arc (CA) graph is the intersection graph of arcs on a circle. A Helly circular-arc (HCA) graph is a CA graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph.
In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a \(\overline{3K_2}\)-free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is \(O(n)\). This represents an improvement over the existing algorithm by V. Guruswami and C. Pandu Rangan [Algorithmic aspects of clique-transversal and clique-independent sets, Discrete Appl. Math. 100, No. 3, 183–202 (2000; Zbl 0948.68135)], whose complexity is \(O(n^2)\). These algorithms suppose that an HCA model of the graph is given.

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI
[1] Balachandran, V.; Nagavamsi, P.; Pandu Rangan, C., Clique transversal and clique independence on comparability graphs, Inform. process. lett., 58, 181-184, (1996)
[2] Bonomo, F., Self-clique Helly circular-arc graphs, Discrete math., 306, 6, 595-597, (2006) · Zbl 1087.05042
[3] Bonomo, F.; Durán, G.; Lin, M.C.; Szwarcfiter, J.L., On balanced graphs, Math. programming, 105, 233-250, (2006) · Zbl 1080.05058
[4] Brandstädt, A.; Chepoi, V.D.; Dragan, F.F.; Voloshin, V.I., Dually chordal graphs, SIAM J. discrete math., 11, 109-127, (1998)
[5] Chang, G.J.; Farber, M.; Tuza, Zs., Algorithmic aspects of neighbourhood numbers, SIAM J. discrete math., 6, 24-29, (1993) · Zbl 0777.05085
[6] Dahlhaus, E.; Manuel, P.D.; Miller, M., Maximum h-colourable subgraph problem in balanced graphs, Inform. process. lett., 65, 301-303, (1998) · Zbl 1338.68098
[7] Duffus, D.; Kiersted, H.A.; Trotter, W.T., Fibers and ordered set coloring, J. combin. theory A, 58, 158-164, (1991) · Zbl 0757.06001
[8] Durán, G.; Lin, M.C., Clique graphs of Helly circular-arc graphs, Ars combin., 60, 255-271, (2001) · Zbl 1072.05565
[9] Durán, G.; Lin, M.C.; Mera, S.; Szwarcfiter, J.L., Clique-independent sets of Helly circular-arc graphs, Electr. notes discrete math., 18, 41-46, (2004)
[10] Durán, G.; Lin, M.C.; Szwarcfiter, J.L., On clique-transversals and clique-independent sets, Ann. oper. res., 116, 71-77, (2002) · Zbl 1013.90107
[11] Gavril, F., Algorithms on circular-arc graphs, Networks, 4, 357-369, (1974) · Zbl 0309.05126
[12] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[13] Golumbic, M.C.; Hammer, P., Stability in circular-arc graphs, J. algorithms, 9, 314-320, (1988) · Zbl 0651.68083
[14] Guruswami, V.; Pandu Rangan, C., Algorithmic aspects of clique transversals and clique independent sets, Discrete appl. math., 100, 183-202, (2000) · Zbl 0948.68135
[15] Hsu, W.L.; Tsai, K.H., Linear time algorithms on circular-arc graphs, Inform. process. lett., 40, 123-129, (1991) · Zbl 0748.68044
[16] C.M. Lee, M.S. Chang, S.C. Sheu, The clique transversal and clique independence of distance hereditary graphs, in: Proceedings of the 19th Workshop on Combinatorial Mathematics and Computation Theory, Taiwan, 2002, pp. 64-69.
[17] McConnell, R.M., Linear-time recognition of circular-arc graphs, Algorithmica, 37, 93-147, (2003) · Zbl 1060.68088
[18] Shih, W.K.; Hsu, W.L., An \(\operatorname{O}(n \log n + m \log \log n)\) algorithm for finding a maximum weight clique in circular-arc graphs, Inform. process. lett., 32, 129-134, (1989) · Zbl 0677.68056
[19] Spinrad, J.P., Efficient graph representation, fields institute monographs, (2003), American Mathematical Society Providence, RI
[20] Tucker, A., Characterizing circular-arc graphs, Bull. amer. math. soc., 76, 1257-1260, (1970) · Zbl 0204.24401
[21] Tucker, A., An efficient test for circular-arc graphs, SIAM J. comput., 9, 1-24, (1980) · Zbl 0453.05054
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.