Artículo
Eguía, M.; Soulignac, F.J. "Hereditary biclique-Helly graphs: Recognition and maximal biclique enumeration" (2013) Discrete Mathematics and Theoretical Computer Science. 15(1):55-74
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
A biclique is a set of vertices that induce a complete bipartite graph. A graph G is biclique-Helly when its family of maximal bicliques satisfies the Helly property. If every induced subgraph of G is also biclique-Helly, then G is hereditary biclique-Helly. A graph is C4-dominated when every cycle of length 4 contains a vertex that is dominated by the vertex of the cycle that is not adjacent to it. In this paper we show that the class of hereditary biclique-Helly graphs is formed precisely by those C4-dominated graphs that contain no triangles and no induced cycles of length either 5 or 6. Using this characterization, we develop an algorithm for recognizing hereditary biclique-Helly graphs in O(n2 +αm) time and O(n+m) space. (Here n, m, and α = O(m1/2) are the number of vertices and edges, and the arboricity of the graph, respectively.) As a subprocedure, we show how to recognize those C4-dominated graphs that contain no triangles in O(αm) time and O(n + m) space. Finally, we show how to enumerate all the maximal bicliques of a C4-dominated graph with no triangles in O(n2 + αm) time and O(αm) space. © 2013 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.
Registro:
| Documento: | Artículo |
| Título: | Hereditary biclique-Helly graphs: Recognition and maximal biclique enumeration |
| Autor: | Eguía, M.; Soulignac, F.J. |
| Filiación: | Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computación, Argentina |
| Palabras clave: | Domination problems; Hereditary biclique-Helly graphs; Maximal bicliques; Triangle-free graphs; Biclique-helly; Bicliques; Complete bipartite graphs; Domination problem; Helly properties; Induced cycle; Induced subgraphs; Triangle-free graphs; Graphic methods; Graph theory |
| Año: | 2013 |
| Volumen: | 15 |
| Número: | 1 |
| Página de inicio: | 55 |
| Página de fin: | 74 |
| Título revista: | Discrete Mathematics and Theoretical Computer Science |
| Título revista abreviado: | Discrete Math. Theor. Comput. Sci. |
| ISSN: | 14627264 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n1_p55_Eguia |
Referencias:
- Chiba, N., Nishizeki, T., Arboricity and subgraph listing algorithms (1985) SIAM J. Comput., 14 (1), pp. 210-223
- Dias, V.M.F., De Figueiredo, C.M.H., Szwarcfiter, J.L., Generating bicliques of a graph in lexicographic order (2005) Theoretical Computer Science, 337 (1-3), pp. 240-248. , DOI 10.1016/j.tcs.2005.01.014, PII S030439750500037X
- Dourado, M.C., Protti, F., Szwarcfiter, J.L., Complexity aspects of the Helly property: Graphs and hypergraphs (2009) Electron. J. Comb., DS17, p. 53
- Garey, M.R., Johnson, D.S., (1979) Computers and Intractability, , W. H. Freeman and Co., San Francisco, Calif., A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences
- Gély, A., Nourine, L., Sadi, B., Enumeration aspects of maximal cliques and bicliques (2009) Discrete Appl. Math., 157 (7), pp. 1447-1459
- Groshaus, M., (2006) Bicliques, Cliques, Neighborhoods, and the Helly Property, , PhD thesis, Universidad de Buenos Aires
- Groshaus, M., Montero, L., On the iterated biclique operator (2008) Proceedings of the VI ALIO/EURO Workshop on Applied Combinatorial Optimization, , Isabel Méndez-Díaz and Paula Zabala, editors, pages CD-ROM version
- Groshaus, M., Montero, L., The number of convergent graphs under the biclique operator with no twin vertices is finite (2009) Proceedings of the v Latin-American Algorithms, Graphs and Optimization Symposium - LAGOS' 2009, , Electronic Notes in Disc. Math. Elsevier
- Groshaus, M., Szwarcfiter, J.L., Biclique-Helly graphs (2007) Graphs Combin., 23 (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
- Makino, K., Uno, T., New algorithms for enumerating all maximal cliques (2004) Algorithm Theory-SWAT 2004, 3111, pp. 260-272. , of Lecture Notes in Comput. Sci., Springer, Berlin
- McKee, T.A., McMorris, F.R., (1999) Topics in Intersection Graph Theory, , SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA
- Montero, L., (2008) Convergencia y Divergencia Del Grafo Biclique Iterado, , Master's thesis, Universidad de Buenos Aires
- Nourine, L., Raynaud, O., A fast algorithm for building lattices (1999) Inform. Process. Lett., 71 (5-6), pp. 199-204
- René, P., The maximum edge biclique problem is NP-complete (2003) Discrete Appl. Math., 131 (3), pp. 651-654
- Prisner, E., Bicliques in graphs. I. Bounds on their number (2000) Combinatorica, 20 (1), pp. 109-117
- Szwarcfiter, J.L., A survey on clique graphs (2003) Recent Advances in Algorithms and Combinatorics, 11, pp. 109-136. , C. Linhares Sales and B. Reed, editors, of CMS Books Math./Ouvrages Math. SMC, Springer, New York
- Terlisky, P., (2010) Biclique-coloreo de Grafos, , Master's thesis, Universidad de Buenos Aires
Citas:
---------- APA ----------
Eguía, M. & Soulignac, F.J. (2013) . Hereditary biclique-Helly graphs: Recognition and maximal biclique enumeration. Discrete Mathematics and Theoretical Computer Science, 15(1), 55-74.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n1_p55_Eguia [ ]
---------- CHICAGO ----------
Eguía, M., Soulignac, F.J. "Hereditary biclique-Helly graphs: Recognition and maximal biclique enumeration" . Discrete Mathematics and Theoretical Computer Science 15, no. 1 (2013) : 55-74.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n1_p55_Eguia [ ]
---------- MLA ----------
Eguía, M., Soulignac, F.J. "Hereditary biclique-Helly graphs: Recognition and maximal biclique enumeration" . Discrete Mathematics and Theoretical Computer Science, vol. 15, no. 1, 2013, pp. 55-74.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n1_p55_Eguia [ ]
---------- VANCOUVER ----------
Eguía, M., Soulignac, F.J. Hereditary biclique-Helly graphs: Recognition and maximal biclique enumeration. Discrete Math. Theor. Comput. Sci. 2013;15(1):55-74.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n1_p55_Eguia [ ]
