Artículo
Tight lower bounds on the number of bicliques in false-twin-free graphs
Fecha de publicación:
07/2016
Editorial:
Elsevier Science
Revista:
Theoretical Computer Science
ISSN:
0304-3975
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
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, bounds on the maximum number of bicliques were given. In this paper we study bounds on the minimun 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 for a subclass of {C4,false-twin}-free graphs and for the class of {K3,false-twin}-free graphs. Finally we discuss the problem for general graphs.
Palabras clave:
Bicliques
,
False-Twin-Free Graphs
,
Lower Bounds
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Groshaus, Marina Esther; Montero, Leandro Pedro; Tight lower bounds on the number of bicliques in false-twin-free graphs; Elsevier Science; Theoretical Computer Science; 636; 7-2016; 77-84
Compartir
Altmétricas