ALGORITHMS FOR RECOGNIZING BIPARTITE-HELLY AND BIPARTITE-CONFORMAL HYPERGRAPHS

作者：Groshaus Marina^*; Szwarcfiter Jayme Luis

来源：RAIRO - Operations Research, 2011, 45(3): 209-222.

DOI：10.1051/ro/2011112

• Algorithms
• bipartite graphs
• biclique-Helly
• biclique matrices
• clique matrices
• Helly property
• hypergraphs

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.

• 出版日期2011-7