Navegar

Colección

Datos Estadísticas

Artículo

Joeris, B.L.; Lin, M.C.; McConnell, R.M.; Spinrad, J.P.; Szwarcfiter, J.L. "Linear-time recognition of Helly circular-arc models and graphs" (2011) Algorithmica (New York). 59(2):215-239
La versión final de este artículo es de uso interno de la institución.
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A circular-arc model M is a circle C together with a collection A of arcs of C. If A satisfies the Helly Property then · 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 algorithms 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(n 3). 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. © 2009 Springer Science+Business Media, LLC.

Registro:

Documento: Artículo
Título:Linear-time recognition of Helly circular-arc models and graphs
Autor:Joeris, B.L.; Lin, M.C.; McConnell, R.M.; Spinrad, J.P.; Szwarcfiter, J.L.
Filiación:Computer Science Department, Colorado State University, Fort Collins, CO 80523-1873, United States
Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
Computer Science Department, Vanderbilt University, Nashville, TN 37235, United States
Instituto de Matemática, NCE and COPPE, Universidade Federal Do Rio de Janeiro, Caixa Postal 2324, Rio de Janeiro, RJ 20001-970, Brazil
Palabras clave:Algorithms; Circular-arc graphs; Forbidden subgraphs; Helly circular-arc graphs; Arc models; Circular-arc graph; Forbidden induced subgraphs; Forbidden subgraphs; General class; Intersection graph; Recognition algorithm; Algorithms; Characterization; Graphic methods
Año:2011
Volumen:59
Número:2
Página de inicio:215
Página de fin:239
DOI: http://dx.doi.org/10.1007/s00453-009-9304-5
Título revista:Algorithmica (New York)
Título revista abreviado:Algorithmica (New York)
ISSN:01784617
CODEN:ALGOE
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v59_n2_p215_Joeris

Referencias:

  • Benzer, S., On the topology of the genetic fine structure (1959) Proc. Natl. Acad. Sci. USA, 45, pp. 1607-1620. , 10.1073/pnas.45.11.1607
  • Booth, S., Lueker, S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms (1976) J. Comput. Syst. Sci., 13, pp. 335-379. , 0367.68034 10.1016/S0022-0000(76)80045-1 433962
  • Deng, X., Hell, P., Huang, J., Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs (1996) SIAM Journal on Computing, 25 (2), pp. 390-403
  • Gabow, H.N., Tarjan, R.E., A linear-time algorithm for a special case of disjoint set union (1985) J. Comput. Syst. Sci., 30, pp. 209-221. , 0572.68058 10.1016/0022-0000(85)90014-5 801823
  • Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369. , 0309.05126 10.1002/net.3230040407 376439
  • Golumbic, M.C., (2004) Algorithmic Graph Theory and Perfect Graphs, , 2 Academic Press New York 1050.05002
  • Habib, M., McConnell, R., Paul, C., Viennot, L., Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing (2000) Theor. Comput. Sci., 234, pp. 59-84. , 0945.68189 10.1016/S0304-3975(97)00241-7 1745069
  • Itai, A., Linear time restricted union/find (2006) Manuscript
  • Kaplan, H., Nussbaum, Y., A simpler linear-time recognition of circular-arc graphs (2006) The Tenth Scandinavian Workshop on Algorithm Theory (SWAT'06) Lecture Notes in Computer Science, 4059, pp. 289-300. , Springer Berlin
  • Kaplan, H., Nussbaum, Y., Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs (2006) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), LNCS4271, pp. 289-300. , Graph-Theoretic Concepts in Computer Science - 32nd International Workshop, WG 2006, Revised Papers
  • Kleinberg, J., Tardos, E., (2006) Algorithm Design, , Addison-Wesley Boston
  • Lekkerker, C.G., Boland, J.C., Representation of finite graphs by a set of intervals on the real line (1962) Fund. Math., 51, pp. 45-64. , 139159
  • Lin, M.C., Szwarcfiter, J.L., Characterizations and linear time recognition of helly circular-arc graphs (2006) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), LNCS4112, pp. 73-82. , Computing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings
  • Lin, M.C., Szwarcfiter, J.L., Efficient construction of unit circular-arc models (2006) Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 309-315. , Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
  • Lin, M.C., Szwarcfiter, J.L., Unit circular-arc graph representations and feasible circulations (2008) SIAM J. Discrete Math., 22, pp. 409-423. , 05529239 10.1137/060650805 2399252
  • McConnell, R.M., Linear-time recognition of circular-arc graphs (2001) Annual Symposium on Foundations of Computer Science - Proceedings, pp. 386-394
  • McConnell, R.M., Linear-time recognition of circular-arc graphs (2003) Algorithmica, 37 (2), pp. 93-147. , 1060.68088 10.1007/s00453-003-1032-7 1993248
  • Roberts, F.S., (1978) Graph Theory and Its Applications to Problems of Society, , Society for Industrial and Applied Mathematics Philadelphia
  • Spinrad, J., (2003) Efficient Graph Representations, , Am. Math. Soc. Providence 1033.05001
  • Tucker, A., Characterizing circular-arc graphs (1970) Bull. Am. Math. Soc., 76, pp. 1257-1260. , 0204.24401 10.1090/S0002-9904-1970-12628-3
  • Tucker, A., An efficient test for circular-arc graphs (1980) SIAM J. Comput., 9, pp. 1-24. , 0453.05054 10.1137/0209001 557822

Citas:

---------- APA ----------
Joeris, B.L., Lin, M.C., McConnell, R.M., Spinrad, J.P. & Szwarcfiter, J.L. (2011) . Linear-time recognition of Helly circular-arc models and graphs. Algorithmica (New York), 59(2), 215-239.
http://dx.doi.org/10.1007/s00453-009-9304-5
---------- CHICAGO ----------
Joeris, B.L., Lin, M.C., McConnell, R.M., Spinrad, J.P., Szwarcfiter, J.L. "Linear-time recognition of Helly circular-arc models and graphs" . Algorithmica (New York) 59, no. 2 (2011) : 215-239.
http://dx.doi.org/10.1007/s00453-009-9304-5
---------- MLA ----------
Joeris, B.L., Lin, M.C., McConnell, R.M., Spinrad, J.P., Szwarcfiter, J.L. "Linear-time recognition of Helly circular-arc models and graphs" . Algorithmica (New York), vol. 59, no. 2, 2011, pp. 215-239.
http://dx.doi.org/10.1007/s00453-009-9304-5
---------- VANCOUVER ----------
Joeris, B.L., Lin, M.C., McConnell, R.M., Spinrad, J.P., Szwarcfiter, J.L. Linear-time recognition of Helly circular-arc models and graphs. Algorithmica (New York). 2011;59(2):215-239.
http://dx.doi.org/10.1007/s00453-009-9304-5