Navegar

Colección

Datos Estadísticas

Artículo

Groshaus, M.; Lin, M.C.; Szwarcfiter, J.L. "On neighborhood-Helly graphs" (2017) Discrete Applied Mathematics. 216:191-202
El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A family F of subsets of some set is intersecting when sets of F pairwise intersect. The family F is Helly when every intersecting subfamily of it contains a common element. In this paper we examine the families of vertex neighborhoods of a graph, with the aim of determining whether or not they are Helly, and also whether or nor they are hereditary Helly, that is, each of the induced subgraphs of the graph is Helly. We examine the cases where the neighborhoods are all open, or all closed, or mixed, that is, some open and some closed. For mixed neighborhoods there are two different kinds of choice of the neighborhood of each vertex to be considered: fixed or arbitrary choice. By fixed mixed neighborhood, we mean that the choice, open or closed, for the neighborhood of a vertex is known in advance, that is part of the input. On the other hand, an arbitrary choice implies that the choice can be made along the process. For the cases of open, closed and fixed mixed neighborhoods, we describe characterizations, both for the neighborhoods to be Helly and hereditary Helly. The characterizations are of two types: based on the concept of extensions, or, for the hereditary cases, by forbidden induced subgraphs. Polynomial time recognition algorithms follow directly from the characterizations. In contrast, for arbitrary mixed neighborhoods, we prove that it is NP-complete to decide whether the family of neighborhoods is Helly or hereditary Helly. © 2016 Elsevier B.V.

Registro:

Documento: Artículo
Título:On neighborhood-Helly graphs
Autor:Groshaus, M.; Lin, M.C.; Szwarcfiter, J.L.
Filiación:Departamento de Computación, Universidad de Buenos Aires, Argentina
Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina
Instituto de Cálculo and Departamento de Computación, Universidad de Buenos Aires, Argentina
Inst Matemática, COPPE and NCE, Universidade Federal do Rio de Janeiro, Brazil
Instituto Nacional de Metrologia, Qualidade e Tecnologia, Brazil
Palabras clave:Complexity; Extensions; Helly property; NP-hardness; Characterization; Polynomial approximation; Complexity; Extensions; Forbidden induced subgraphs; Helly properties; Induced subgraphs; NP-hardness; Polynomial-time; Recognition algorithm; Fluorine
Año:2017
Volumen:216
Página de inicio:191
Página de fin:202
DOI: http://dx.doi.org/10.1016/j.dam.2016.04.029
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v216_n_p191_Groshaus

Referencias:

  • Bandelt, H.J., Farber, M., Hell, P., Absolute reflexive retracts and absolute bipartite retracts (1993) Discrete Appl. Math., 44, pp. 9-20
  • Bandelt, H.J., Pesch, E., Dismantling absolute retracts of reflexive graphs (1989) European J. Combin., 10, pp. 210-220
  • Bandelt, H.J., Pesch, E., Efficient characterizations of n-chromatic absolute retracts (1991) J. Combin. Theory Ser. B, 53, pp. 5-31
  • Bandelt, H.J., Prisner, E., Clique graphs and Helly graphs (1991) J. Combin. Theory Ser. B, 51, pp. 34-45
  • Berge, C., Graphes et Hypergraphes (1970), Dunod Paris Graphs and Hypergraphs, North-Holland, Amsterdam, 1973, revised translation; Berge, C., Hypergraphs (1987), Gauthier-Villars Paris; Berge, C., Duchet, P., A generalization of Gilmore's theorem (1975) Recent Advances in Graph Theory, pp. 49-55. , M. Fiedler Acad. Praha Prague
  • Bollobás, B., Combinatorics (1986), Cambridge University Press Cambridge; Brandstädt, A., Chepoi, V., Dragan, F., Voloshin, V., Dually chordal graphs (1998) SIAM J. Discrete Math., 11 (3), pp. 437-455
  • Brandstädt, A., Le, V.B., Spinrad, J.P., Graph classes: A survey (1999) SIAM Monographs on Discrete Mathematics and Applications, , Society for Industrial and Applied Mathematics Philadelphia, PA
  • Bretto, A., Ubéda, S., Žerovnik, J., A polynomial algorithm for the strong Helly property (2002) Inform. Process. Lett., 81, pp. 55-57
  • Daligault, J., Gonçalves, D., Rao, M., Diamond-free circle graphs are Helly circle (2010) Discrete Math., 310, pp. 845-849
  • Dourado, M.C., Lin, M.C., Protti, F., Szwarcfiter, J.L., Improved algorithms for recognizing p-Helly and hereditary p-Helly hypergraphs (2008) Inform. Process. Lett., 108, pp. 247-250
  • Dourado, M.C., Protti, F., Szwarcfiter, J.L., Complexity aspects of the Helly property: Graphs and hypergraphs (2009) Electron. J. Combin., , Dynamic Survey #DS17
  • Dragan, F.F., Centers of graphs and the helly property (1989), (Ph.D. thesis) Moldava State University Chisinaˇu (in Russian); Dragan, F.F., Domination in Helly graphs without quadrangles (1993) Cybernet. Systems Anal. (Kiev), 6. , (in Russian)
  • Dragan, F.F., Brandstädt, A., r-Dominating cliques in graphs with hypertree structure (1996) Discrete Math., 162, pp. 93-108
  • Dragan, F.F., Prisacaru, C.F., Chepoi, V.D., Location problems in graphs and the Helly property (1992) Diskret. Mat. (Moscow), 4, pp. 67-73. , (in Russian)
  • Duchet, P., Proprieté de Helly et problèmes de représentations (1976) Problèmes Combinatoires et Théorie de Graphs, Colloquium International CNRS, 260, pp. 117-118. , CNRS Orsay, France
  • Duchet, P., Hypergraphs (1995) Handbook of Combinatorics, volume 1, pp. 381-432. , R.L. Graham M. Grötschel L. Lovász Elsevier North-Holland Amsterdam-New York-Oxford
  • Flament, C., Hypergraphes arborés (1978) Discrete Math., 21, pp. 223-226
  • Gavril, F., Algorithms on circular-arc graphs (1974) Networks, 4, pp. 357-369
  • Golumbic, M.C., Jamison, R.E., The edge intersection graphs of paths in a tree (1985) J. Combin. Theory Ser. B, 38, pp. 8-22
  • Groshaus, M., Szwarcfiter, J.L., Biclique-Helly graphs (2007) Graphs Combin., 26 (6), pp. 633-645
  • Groshaus, M., Szwarcfiter, J.L., On hereditary Helly classes of graphs (2008) Discrete Math. Theor. Comput. Sci., 10 (1), pp. 71-78
  • Groshaus, M., Szwarcfiter, J.L., Biclique graphs and biclique matrices (2010) J. Graph Theory, 63 (1), pp. 1-16
  • Hell, P., Rétractions de graphes (1972), (Ph.D. thesis) Université de Montreal; Joeris, B., Lin, M.C., McConnell, R.M., Spinrad, J., Szwarcfiter, J.L., Linear time recognition of Helly circular-arc graphs and models (2011) Algorithmica, 59 (2), pp. 215-239
  • Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L., Normal Helly circular-arc graphs and its subclasses (2013) Discrete Appl. Math., 161, pp. 1037-1059
  • Lin, M.C., Szwarcfiter, J.L., Faster recognition of Clique-Helly and Hereditary Clique-Helly graphs (2007) Inform. Process. Lett., 103 (1), pp. 40-43
  • Mckee, T.A., McMorris, F.R., Topics in Intersection Graph Theory (1999), SIAM Monographs on Discrete Mathematics and Applications Philadelphia, PA; Papadimitriou, C.H., Computational Complexity (1994), Addison Wesley; Prisner, E., Hereditary clique-Helly graphs (1993) J. Combin. Math. Combin. Comput., 14, pp. 216-220
  • Prisner, E., Graph Dynamics (1995), Pitman Research Notes in Mathematics Longman; Szwarcfiter, J.L., Recognizing clique Helly graphs (1997) Ars Combin., 45, pp. 29-32
  • Wallis, W.D., Zhang, G.H., On maximal clique irreducible graphs graphs (1990) J. Combin. Math. Combin. Comput., 8, pp. 187-193

Citas:

---------- APA ----------
Groshaus, M., Lin, M.C. & Szwarcfiter, J.L. (2017) . On neighborhood-Helly graphs. Discrete Applied Mathematics, 216, 191-202.
http://dx.doi.org/10.1016/j.dam.2016.04.029
---------- CHICAGO ----------
Groshaus, M., Lin, M.C., Szwarcfiter, J.L. "On neighborhood-Helly graphs" . Discrete Applied Mathematics 216 (2017) : 191-202.
http://dx.doi.org/10.1016/j.dam.2016.04.029
---------- MLA ----------
Groshaus, M., Lin, M.C., Szwarcfiter, J.L. "On neighborhood-Helly graphs" . Discrete Applied Mathematics, vol. 216, 2017, pp. 191-202.
http://dx.doi.org/10.1016/j.dam.2016.04.029
---------- VANCOUVER ----------
Groshaus, M., Lin, M.C., Szwarcfiter, J.L. On neighborhood-Helly graphs. Discrete Appl Math. 2017;216:191-202.
http://dx.doi.org/10.1016/j.dam.2016.04.029