Artículo
Abstract:
A circular-arc graph is the intersection graph of arcs of a circle. A Helly circular-arc graph is a circular-arc 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 algorithms for finding the maximum cardinality and weight of a clique-independent set of a over(3 K2, -)-free CA graph. Also, we apply the algorithms to the special case of an H C A graph. The complexity of the proposed algorithm for the cardinality problem in H C A graphs is O(n). This represents an improvement over the existing algorithm, whose complexity is O (n2). © 2005 Elsevier B.V. All rights reserved.
Registro:
| Documento: | Artículo |
| Título: | Clique-independent sets of Helly circular-arc graphs |
| Autor: | Durán, G.; Lin, M.C.; Mera, S.; Szwarcfiter, J.L. |
| Filiación: | Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina Instituto de Matemática, NCE, COPPE, Rio de Janeiro, Brazil |
| Palabras clave: | algorithms; circular-arc graphs; clique-independent sets; Helly circular-arc graphs |
| Año: | 2004 |
| Volumen: | 18 |
| Página de inicio: | 103 |
| Página de fin: | 108 |
| DOI: | http://dx.doi.org/10.1016/j.endm.2004.06.016 |
| Título revista: | Electronic Notes in Discrete Mathematics |
| Título revista abreviado: | Electron. Notes Discrete Math. |
| ISSN: | 15710653 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v18_n_p103_Duran |
Referencias:
- Duffus, D., Kiersted, H., Trotter, W., Fibers and ordered set coloring (1991) Journal of Combinatorial Theory A, 58, pp. 158-164
- Golumbic, M., Hammer, P., Stability in circular-arc graphs (1988) Journal of Algorithms, 9, pp. 314-320
- Guruswami, V., Pandu Rangan, C., Algorithmic aspects of clique-transversals and clique-independent sets (2000) Discrete Applied Mathematics, 100, pp. 183-202
- Prisner, E., (1995) Graph Theory, Combinatorics and Applications: Proceedings of the 7th. Quadrennial International Conference on the Theory and Applications, pp. 945-956. , Alavi Y., and Schwenk A. (Eds), John Wiley and Sons
- Spinrad, J., (2003) Efficient Graph Representations, , American Mathematical Society, Providence, Rhode Island
- Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, Y., A new algorithm for generating all the maximal independent sets (1977) SIAM Journal on Computing, 6, pp. 505-517
Citas:
---------- APA ----------
Durán, G., Lin, M.C., Mera, S. & Szwarcfiter, J.L. (2004) . Clique-independent sets of Helly circular-arc graphs. Electronic Notes in Discrete Mathematics, 18, 103-108.http://dx.doi.org/10.1016/j.endm.2004.06.016
---------- CHICAGO ----------
Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L. "Clique-independent sets of Helly circular-arc graphs" . Electronic Notes in Discrete Mathematics 18 (2004) : 103-108.http://dx.doi.org/10.1016/j.endm.2004.06.016
---------- MLA ----------
Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L. "Clique-independent sets of Helly circular-arc graphs" . Electronic Notes in Discrete Mathematics, vol. 18, 2004, pp. 103-108.http://dx.doi.org/10.1016/j.endm.2004.06.016
---------- VANCOUVER ----------
Durán, G., Lin, M.C., Mera, S., Szwarcfiter, J.L. Clique-independent sets of Helly circular-arc graphs. Electron. Notes Discrete Math. 2004;18:103-108.http://dx.doi.org/10.1016/j.endm.2004.06.016
