info:eu-repo/semantics/article
Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs
Fecha
2011-07Registro en:
Groshaus, Marina Esther; Szwarcfiter, Jayme Luis; Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs; EDP Sciences; Rairo - Recherche Operationnelle (operations Research); 45; 3; 7-2011; 209-222
0399-0559
CONICET Digital
CONICET
Autor
Groshaus, Marina Esther
Szwarcfiter, Jayme Luis
Resumen
A hypergraph is Helly if every family of hyperedges of it, formed by pairwise intersecting hyperedges, has a common vertex. We consider the concepts of bipartite-conformal and (colored) bipartite-Helly hypergraphs. In the same way as conformal hypergraphs and Helly hypergraphs are dual concepts, bipartite-conformal and bipartite-Helly hypergraphs are also dual. They are useful for characterizing biclique matrices and biclique graphs, that is, the incident biclique-vertex incidence matrix and the intersection graphs of the maximal bicliques of a graph, respectively. These concepts play a similar role for the bicliques of a graph, as do clique matrices and clique graphs, for the cliques of the graph. We describe polynomial time algorithms for recognizing bipartite-conformal and bipartite-Helly hypergraphs as well as biclique matrices.