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 graph is biclique-Helly when its family of (maximal) bicliques is a Helly family. We describe characterizations for biclique-Helly graphs, leading to polynomial time recognition algorithms. In addition, we relate biclique-Helly graphs to the classes of clique-Helly, disk-Helly and neighborhood-Helly graphs. © 2007 Springer-Verlag Tokyo.

Registro:

Documento: Artículo
Título:Biclique-Helly graphs
Autor:Groshaus, M.; Szwarcfiter, J.L.
Filiación:Universidad de Buenos Aires, Facultad de Ciencias Exáctas y Naturales, Departamento de Computación, Argentina
Universidade Federal Do Rio de Janeiro, Instituto de Matemática, NCE and COPPE, Brazil
Palabras clave:Bichromatic cliques; Biclique-Helly graphs; Bicliques; Clique-Helly graphs; Disk-Helly graphs; Neighborhood-Helly graphs
Año:2007
Volumen:23
Número:6
Página de inicio:633
Página de fin:645
DOI: http://dx.doi.org/10.1007/s00373-007-0756-6
Título revista:Graphs and Combinatorics
Título revista abreviado:Graphs Comb.
ISSN:09110119
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09110119_v23_n6_p633_Groshaus

Referencias:

  • Bandelt, H.-J., Farber, M., Hell, P., Absolute reflexive retracts and absolute bipartite graphs (1993) Discrete Applied Mathematics, 44, pp. 9-20
  • Bandelt, H.-J., Pesch, E., Dismantling absolute retracts of reflexive graphs (1989) European J. Combinatorics, 10, pp. 211-220
  • Bandelt, H.-J., Prisner, E., Clique graphs and Helly graphs (1991) J. Combin Theory B, 51, pp. 34-45
  • Berge, C., (1989) Hypergraphs, 45. , North Holland Mathematical Library Elsevier Science Publishers B.V., Amsterdam
  • Berge, C., Duchet, P., A generalization of Gilmore's theorem (1975) Recent Advances in Graph Theory, pp. 49-55. , Fiedler, M. (ed.) Acad. Praha, Prague
  • Bondy, A., Durán, G., Lin, M., Szwarcfiter, J., Self-clique graphs and matrix permutations (2003) Journal of Graph Theory, 44, pp. 178-192
  • Burzyn, P., Bonomo, F., Durán, G., NP-completeness results for edge modification problems (2006) Discrete Applied Mathematics, 154 (13), pp. 1824-1844
  • Dragan, F.F., (1989) Centers of Graphs and the Helly Property, , PhD thesis, Moldava State University, Chisinau, Moldava In russian
  • Escalante, F., Über iterierte Clique-Graphen (1973) Abhandlungender Mathematischen Seminar der Universität Hamburg, 39, pp. 59-68
  • Hamelink, B.C., A partial characterization of clique graphs (1968) J. Combin Theory, 5, pp. 192-197
  • Hell, P., (2003), Personal Communication; 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
  • Müller, H., On edge perfectness and classes of bipartite graphs (1996) Discrete Math., 149, pp. 159-187
  • Peeters, R., The maximum edge biclique problem is NP-complete (2003) Discrete Appl. Math., 131, pp. 651-654
  • Prisner, E., Bicliques in graphs I. Bounds on their number (2000) Combinatorica, 20, pp. 109-117
  • Prisner, E., Bicliques in graphs II. Recognizing k-path graphs and underlying graphs of line digraphs (1997) Graph Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, 1335, pp. 253-287
  • Szwarcfiter, J.L., Recognizing clique-Helly graphs (1997) Ars Combinatoria, 45, pp. 29-32
  • Tuza, Z., Covering of graphs by complete bipartite subgraphs: Complexity of 0-1 matrices (1984) Combinatorica, 4, pp. 111-116
  • Robert, F.S., Spencer, J.H., A characterization of clique graphs (1971) J. Combin. Theory B, 10, pp. 102-108

Citas:

---------- APA ----------
Groshaus, M. & Szwarcfiter, J.L. (2007) . Biclique-Helly graphs. Graphs and Combinatorics, 23(6), 633-645.
http://dx.doi.org/10.1007/s00373-007-0756-6
---------- CHICAGO ----------
Groshaus, M., Szwarcfiter, J.L. "Biclique-Helly graphs" . Graphs and Combinatorics 23, no. 6 (2007) : 633-645.
http://dx.doi.org/10.1007/s00373-007-0756-6
---------- MLA ----------
Groshaus, M., Szwarcfiter, J.L. "Biclique-Helly graphs" . Graphs and Combinatorics, vol. 23, no. 6, 2007, pp. 633-645.
http://dx.doi.org/10.1007/s00373-007-0756-6
---------- VANCOUVER ----------
Groshaus, M., Szwarcfiter, J.L. Biclique-Helly graphs. Graphs Comb. 2007;23(6):633-645.
http://dx.doi.org/10.1007/s00373-007-0756-6