Tight lower bounds on the number of bicliques in false-twin-free graphs

Mostrar todas las versiones(2)

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Groshaus, M., Montero, L.
Formato: JOUR
Materias:
Bicliques
False-twin-free graphs
Lower bounds
Computational methods
Computer science
Biclique
Free graphs
General graph
Induced subgraphs
Twin-free
Graphic methods
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03043975_v636_n_p77_Groshaus
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03043975_v636_n_p77_Groshaus
record_format dspace
spelling todo:paper_03043975_v636_n_p77_Groshaus2023-10-03T15:20:29Z Tight lower bounds on the number of bicliques in false-twin-free graphs Groshaus, M. Montero, L. Bicliques False-twin-free graphs Lower bounds Computational methods Computer science Biclique Bicliques Free graphs General graph Induced subgraphs Lower bounds Twin-free Graphic methods 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. © 2016 Elsevier B.V. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03043975_v636_n_p77_Groshaus
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Bicliques
False-twin-free graphs
Lower bounds
Computational methods
Computer science
Biclique
Bicliques
Free graphs
General graph
Induced subgraphs
Lower bounds
Twin-free
Graphic methods
spellingShingle Bicliques
False-twin-free graphs
Lower bounds
Computational methods
Computer science
Biclique
Bicliques
Free graphs
General graph
Induced subgraphs
Lower bounds
Twin-free
Graphic methods
Groshaus, M.
Montero, L.
Tight lower bounds on the number of bicliques in false-twin-free graphs
topic_facet Bicliques
False-twin-free graphs
Lower bounds
Computational methods
Computer science
Biclique
Bicliques
Free graphs
General graph
Induced subgraphs
Lower bounds
Twin-free
Graphic methods
description 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. © 2016 Elsevier B.V.
format JOUR
author Groshaus, M.
Montero, L.
author_facet Groshaus, M.
Montero, L.
author_sort Groshaus, M.
title Tight lower bounds on the number of bicliques in false-twin-free graphs
title_short Tight lower bounds on the number of bicliques in false-twin-free graphs
title_full Tight lower bounds on the number of bicliques in false-twin-free graphs
title_fullStr Tight lower bounds on the number of bicliques in false-twin-free graphs
title_full_unstemmed Tight lower bounds on the number of bicliques in false-twin-free graphs
title_sort tight lower bounds on the number of bicliques in false-twin-free graphs
url http://hdl.handle.net/20.500.12110/paper_03043975_v636_n_p77_Groshaus
work_keys_str_mv AT groshausm tightlowerboundsonthenumberofbicliquesinfalsetwinfreegraphs
AT monterol tightlowerboundsonthenumberofbicliquesinfalsetwinfreegraphs
_version_ 1807321416384643072

Ejemplares similares