Navegar

Colección

Datos Estadísticas

Artículo

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 biclique is a maximal bipartite complete induced subgraph of G. Bicliques have been studied in the last years motivated by the large number of applications. In particular, enumeration of the maximal bicliques has been of interest in data analysis. Associated with this issue, upper and lower bounds on the maximun number of bicliques were given. In this paper we study lower bounds on the number of bicliques of a graph. Since adding false-twin vertices to G does not change the number of bicliques, we restrict to false-twin-free graphs. We give a tight lower bound on the minimum number bicliques in {C4,diamond,false-twin}-free graphs, (K3,false-twin)-free graphs and we present some conjectures for general false-twin-free graphs. © 2015 Elsevier B.V.

Registro:

Documento: Artículo
Título:Tight lower bounds on the number of bicliques in false-twin-free graphs
Autor:Groshaus, M.; Montero, L.
Filiación:Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina
Laboratoire de Recherche en Informatique, Université Paris-Sud, Orsay CEDEX, France
Palabras clave:Bicliques; False-twin-free graphs; Lower bounds
Año:2015
Volumen:50
Página de inicio:293
Página de fin:298
DOI: http://dx.doi.org/10.1016/j.endm.2015.07.049
Título revista:Electronic Notes in Discrete Mathematics
Título revista abreviado:Electron. Notes Discrete Math.
ISSN:15710653
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v50_n_p293_Groshaus

Referencias:

  • Amilhastre, J., Vilarem, M.C., Janssen, P., Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs (1998) Discrete Appl. Math., 86, pp. 125-144
  • Ganter, B., Wille, R., (1999) Formal concept analysis, , Springer-Verlag, Berlin, x+284 pp
  • Gaspers, S., Kratsch, D., Liedloff, M., On independent sets and bicliques in graphs (2008) Lecture Notes in Computer Science, 5344, pp. 171-182. , Springer, Berlin Heidelberg, Graph-Theoretic Concepts in Computer Science
  • Groshaus, M., Montero, L., On the iterated biclique operator (2013) J. Graph Theory, 73, pp. 181-190
  • Prisner, E., Bicliques in graphs i: Bounds on their number (2000) Combinatorica, 20, pp. 109-117

Citas:

---------- APA ----------
Groshaus, M. & Montero, L. (2015) . Tight lower bounds on the number of bicliques in false-twin-free graphs. Electronic Notes in Discrete Mathematics, 50, 293-298.
http://dx.doi.org/10.1016/j.endm.2015.07.049
---------- CHICAGO ----------
Groshaus, M., Montero, L. "Tight lower bounds on the number of bicliques in false-twin-free graphs" . Electronic Notes in Discrete Mathematics 50 (2015) : 293-298.
http://dx.doi.org/10.1016/j.endm.2015.07.049
---------- MLA ----------
Groshaus, M., Montero, L. "Tight lower bounds on the number of bicliques in false-twin-free graphs" . Electronic Notes in Discrete Mathematics, vol. 50, 2015, pp. 293-298.
http://dx.doi.org/10.1016/j.endm.2015.07.049
---------- VANCOUVER ----------
Groshaus, M., Montero, L. Tight lower bounds on the number of bicliques in false-twin-free graphs. Electron. Notes Discrete Math. 2015;50:293-298.
http://dx.doi.org/10.1016/j.endm.2015.07.049