zbMATH — the first resource for mathematics

Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs. (English) Zbl 1247.05239
Summary: 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.
05C85 Graph algorithms (graph-theoretic aspects)
05C65 Hypergraphs
Full Text: DOI EuDML
[1] J. Amilhastre, M.C. Vilarem and P. Janssen, Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs. Discrete Appl. Math.86 (1998) 125-144. Zbl0906.05067 · Zbl 0906.05067
[2] C. Berge, Hypergraphs. Elsevier Science Publishers (1989).
[3] V.M.F. Dias, C.M.H. Figueiredo and J.L. Szwarcfiter, Generating bicliques in lexicographic order. Theoret. Comput. Sci.337 (2005) 240-248. Zbl1076.68048 · Zbl 1076.68048
[4] F. Gavril, Algorithms on circular-arc graphs. Networks4 (1974) 357-369. · Zbl 0309.05126
[5] P.C. Gilmore and A.J. Hoffman, A characterization of comparability graphs and of interval graphs. Canadian J. Math.16 (1964) 539-548. Zbl0121.26003 · Zbl 0121.26003
[6] M. Groshaus and J.L. Szwarcfiter, Biclique-Helly graphs. Graphs Combin.23 (2007) 633-645. · Zbl 1140.05314
[7] M. Groshaus and J.L. Szwarcfiter, On hereditary Helly classes of graphs. Discrete Math. Theor. Comput. Sci.10 (2008) 71-78. · Zbl 1153.05059
[8] M. Groshaus and J.L. Szwarcfiter, Biclique graphs and biclique matrices. J. Graph Theory63 (2010) 1-16. Zbl1216.05104 · Zbl 1216.05104
[9] F. Larrión, V. Neumann-Lara, M.A. Pizaña and T.D. Porter, A hierarchy of self-clique graphs. Discrete Mathematics282 (2004) 193-208. Zbl1042.05073 · Zbl 1042.05073
[10] Zs. Tuza, Covering of graphs by complete bipartite subgraphs: complexity of {0,1} matrices. Combinatorica4 (1984) 111-116. Zbl0559.05050 · Zbl 0559.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.