Characterizations and linear time recognition of helly circular-arc graphs
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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Acta de conferencia Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Springer Verlag
2006
|
| Acceso en línea: | Registro en Scopus Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 04981caa a22006017a 4500 | ||
|---|---|---|---|
| 001 | PAPER-6934 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203639.0 | ||
| 008 | 190411s2006 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-33749580075 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Lin, M.C. | |
| 245 | 1 | 0 | |a Characterizations and linear time recognition of helly circular-arc graphs |
| 260 | |b Springer Verlag |c 2006 | ||
| 270 | 1 | 0 | |m Lin, M.C.; Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, Argentina; email: oscarlin@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a 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 | ||
| 504 | |a Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369 | ||
| 504 | |a Golumbic, M.C., (1980) Algorithmic Graph Theory and Perfect Graphs, , Academic Press, 2nd ed. 2004 | ||
| 504 | |a 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 | ||
| 504 | |a Kaplan, H., Nussbaum, Y., A simpler linear-time recognition of circular-arc graphs (2006) 10th Scandinavian Workshop on Algorithm Theory, , accepted for publication in | ||
| 504 | |a 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 | ||
| 504 | |a McConnell, R.M., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37 (2), pp. 93-147 | ||
| 504 | |a Spinrad, J., Efficient graph representations (2003) American Mathematical Society | ||
| 504 | |a Tucker, A., Characterizing circular-arc graphs (1970) Bull. American Mathematical Society, 76, pp. 1257-1260A4 - | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Buenos Aires, Argentina | ||
| 593 | |a Universidade Federal do Rio de Janeiro, Instituto de Matemática, COPPE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil | ||
| 690 | 1 | 0 | |a ALGORITHMS |
| 690 | 1 | 0 | |a CIRCULAR-ARC GRAPHS |
| 690 | 1 | 0 | |a FORBIDDEN SUBGRAPHS |
| 690 | 1 | 0 | |a HELLY CIRCULAR-ARC GRAPHS |
| 690 | 1 | 0 | |a ALGORITHMS |
| 690 | 1 | 0 | |a COMPUTATIONAL COMPLEXITY |
| 690 | 1 | 0 | |a COMPUTATIONAL METHODS |
| 690 | 1 | 0 | |a GRAPHIC METHODS |
| 690 | 1 | 0 | |a MATHEMATICAL MODELS |
| 690 | 1 | 0 | |a TIME SERIES ANALYSIS |
| 690 | 1 | 0 | |a CIRCULAR-ARC GRAPHS |
| 690 | 1 | 0 | |a FORBIDDEN SUBGRAPHS |
| 690 | 1 | 0 | |a HELLY CIRCULAR-ARC MODEL |
| 690 | 1 | 0 | |a RECOGNITION ALGORITHMS |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 700 | 1 | |a Szwarcfiter, J.L. | |
| 711 | 2 | |c Taipei |d 15 August 2006 through 18 August 2006 |g Código de la conferencia: 68290 | |
| 773 | 0 | |d Springer Verlag, 2006 |g v. 4112 LNCS |h pp. 73-82 |p Lect. Notes Comput. Sci. |n Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |x 03029743 |w (AR-BaUEN)CENRE-983 |z 3540369252 |z 9783540369257 |t 12th Annual International Conference on Computing and Combinatorics, COCOON 2006 | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-33749580075&partnerID=40&md5=b3af274a99b4f0352a74e07f1e92eeba |y Registro en Scopus |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_03029743_v4112LNCS_n_p73_Lin |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v4112LNCS_n_p73_Lin |y Registro en la Biblioteca Digital |
| 961 | |a paper_03029743_v4112LNCS_n_p73_Lin |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 67887 | ||