Navegar

Colección

Datos Estadísticas

Artículo

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 family of subsets of a set is Helly when every subfamily of it, which is formed by pairwise intersecting subsets contains a common element. A graph G is clique-Helly when the family of its (maximal) cliques is Helly, while G is hereditary clique-Helly when every induced subgraph of it is clique-Helly. The best algorithms currently known to recognize clique-Helly and hereditary clique-Helly graphs have complexities O (n m2) and O (n2 m), respectively, for a graph with n vertices and m edges. In this Note, we describe algorithms which recognize both classes in O (m2) time. These algorithms also reduce the complexity of recognizing some other classes, as disk-Helly graphs. © 2007 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Faster recognition of clique-Helly and hereditary clique-Helly graphs
Autor:Lin, M.C.; Szwarcfiter, J.L.
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, NCE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brazil
Palabras clave:Algorithms; Clique-Helly graphs; Disk-Helly graphs; Helly property; Hereditary clique-Helly graphs; Hereditary disk-Helly graphs; Algorithms; Computational complexity; Computational methods; Set theory; Clique-Helly graphs; Disk-Helly graphs; Helly property; Hereditary clique Helly graphs; Hereditary disk Helly graphs; Graph theory
Año:2007
Volumen:103
Número:1
Página de inicio:40
Página de fin:43
DOI: http://dx.doi.org/10.1016/j.ipl.2007.02.017
Título revista:Information Processing Letters
Título revista abreviado:Inf. Process. Lett.
ISSN:00200190
CODEN:IFPLA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v103_n1_p40_Lin

Referencias:

  • Bandelt, H.J., Pesch, E., Dismantling absolute retracts of reflexive graphs (1989) European Journal Combinatorics, 10, pp. 211-220
  • Bandelt, H.J., Prisner, E., Clique graphs and Helly graphs (1991) Journal of Combinatorial Theory B, 51, pp. 34-45
  • Berge, C., (1970) Graphes et Hypergraphes, , Dunod, Paris
  • Bondy, A., Durán, G., Lin, M., Szwarcfiter, J.L., Self-clique graphs and matrix permutations (2003) Journal of Graph Theory, 44, pp. 178-192
  • Bonomo, F., Chudnowsky, M., Durán, G., Partial characterizations of clique-perfect graphs (2005) Electronic Notes in Discrete Mathematics, 19, pp. 95-101
  • Brandstädt, A., Le, V., Spinrad, J., Graph Classes: A Survey (1999) SIAM Monographs on Discrete Mathematics and Applications, , SIAM Publications, Philadelphia
  • Bretto, A., Ubéda, S., Zerovnik, J., A polynomial algorithm for the strong Helly property (2002) Information Processing Letters, 81, pp. 55-57
  • Escalante, F., Über iterierte Clique-Graphen (1973) Abhandlungen des Mathematischen Seminars der Universität Hamburg, 39, pp. 59-68
  • Hamelink, B.C., A partial characterization of clique graphs (1968) Journal of Combinatorial Theory, 5, pp. 192-197
  • Larrión, F., Neumann-Lara, V., Pizaña, M.A., Porter, T.D., A hierarchy of self-clique graphs (2004) Discrete Mathematics, 282, pp. 193-208
  • Nowakowski, R., Winkler, P., Vertex to vertex pursuit of a graph (1983) Discrete Mathematics, 43, pp. 235-239
  • Prisner, E., Hereditary clique-Helly graphs (1993) Journal of Combinatorial Mathematics and Combinatorial Computing, 14, pp. 216-220
  • Roberts, F.S., Spencer, J.H., A characterization of clique graphs (1971) Journal of Combinatorial Theory B, 10, pp. 102-108
  • Szwarcfiter, J.L., Recognizing clique-Helly graphs (1997) Ars Combinatoria, 45, pp. 29-32
  • Wallis, W.D., Zhang, G.H., On clique-irreducible graphs (1990) Journal of Combinatorial Mathematics and Combinatorial Computing, 8, pp. 187-193

Citas:

---------- APA ----------
Lin, M.C. & Szwarcfiter, J.L. (2007) . Faster recognition of clique-Helly and hereditary clique-Helly graphs. Information Processing Letters, 103(1), 40-43.
http://dx.doi.org/10.1016/j.ipl.2007.02.017
---------- CHICAGO ----------
Lin, M.C., Szwarcfiter, J.L. "Faster recognition of clique-Helly and hereditary clique-Helly graphs" . Information Processing Letters 103, no. 1 (2007) : 40-43.
http://dx.doi.org/10.1016/j.ipl.2007.02.017
---------- MLA ----------
Lin, M.C., Szwarcfiter, J.L. "Faster recognition of clique-Helly and hereditary clique-Helly graphs" . Information Processing Letters, vol. 103, no. 1, 2007, pp. 40-43.
http://dx.doi.org/10.1016/j.ipl.2007.02.017
---------- VANCOUVER ----------
Lin, M.C., Szwarcfiter, J.L. Faster recognition of clique-Helly and hereditary clique-Helly graphs. Inf. Process. Lett. 2007;103(1):40-43.
http://dx.doi.org/10.1016/j.ipl.2007.02.017