Artículo
Abstract:
A circular-arc model (C, A) is a circle C together with a collection A of arcs of C. If A satisfies the Helly Property then (C, A) is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention, in the literature. Linear time recognition algorithm have been described both for the general class and for some of its subclasses. However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n3). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound. © Springer-Verlag Berlin Heidelberg 2006.
Registro:
| Documento: | Artículo |
| Título: | Characterizations and linear time recognition of helly circular-arc graphs |
| Autor: | Lin, M.C.; Szwarcfiter, J.L. |
| Ciudad: | Taipei |
| Filiación: | Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, Argentina Universidade Federal do Rio de Janeiro, Instituto de Matemática, COPPE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil |
| Palabras clave: | Algorithms; Circular-arc graphs; Forbidden subgraphs; Helly circular-arc graphs; Algorithms; Computational complexity; Computational methods; Graphic methods; Mathematical models; Time series analysis; Circular-arc graphs; Forbidden subgraphs; Helly circular-arc model; Recognition algorithms; Graph theory |
| Año: | 2006 |
| Volumen: | 4112 LNCS |
| Página de inicio: | 73 |
| Página de fin: | 82 |
| Título revista: | 12th Annual International Conference on Computing and Combinatorics, COCOON 2006 |
| Título revista abreviado: | Lect. Notes Comput. Sci. |
| ISSN: | 03029743 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4112LNCS_n_p73_Lin |
Referencias:
- Deng, X., Hell, P., Huang, J., Linear time representation algorithms for proper circular-arc graphs and proper interval graphs (1996) SIAM J. Computing, 25, pp. 390-403
- Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369
- Golumbic, M.C., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press, 2nd ed. 2004
- Habib, M., McConnell, R.M., Paul, C., Viennot, L., Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing (2000) Theoretical Computer Science, 234, pp. 59-84
- Kaplan, H., Nussbaum, Y., A simpler linear-time recognition of circular-arc graphs (2006) 10th Scandinavian Workshop on Algorithm Theory, , accepted for publication in
- Lin, M.C., Szwarcfiter, J.L., Efficient construction of unit circular-arc models (2006) Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 309-315
- McConnell, R.M., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37 (2), pp. 93-147
- Spinrad, J., Efficient graph representations (2003) American Mathematical Society
- Tucker, A., Characterizing circular-arc graphs (1970) Bull. American Mathematical Society, 76, pp. 1257-1260A4 -
Citas:
---------- APA ----------
Lin, M.C. & Szwarcfiter, J.L. (2006) . Characterizations and linear time recognition of helly circular-arc graphs. 12th Annual International Conference on Computing and Combinatorics, COCOON 2006, 4112 LNCS, 73-82.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4112LNCS_n_p73_Lin [ ]
---------- CHICAGO ----------
Lin, M.C., Szwarcfiter, J.L. "Characterizations and linear time recognition of helly circular-arc graphs" . 12th Annual International Conference on Computing and Combinatorics, COCOON 2006 4112 LNCS (2006) : 73-82.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4112LNCS_n_p73_Lin [ ]
---------- MLA ----------
Lin, M.C., Szwarcfiter, J.L. "Characterizations and linear time recognition of helly circular-arc graphs" . 12th Annual International Conference on Computing and Combinatorics, COCOON 2006, vol. 4112 LNCS, 2006, pp. 73-82.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4112LNCS_n_p73_Lin [ ]
---------- VANCOUVER ----------
Lin, M.C., Szwarcfiter, J.L. Characterizations and linear time recognition of helly circular-arc graphs. Lect. Notes Comput. Sci. 2006;4112 LNCS:73-82.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4112LNCS_n_p73_Lin [ ]
