Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 3, pp. 209-222.

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.

DOI : https://doi.org/10.1051/ro/2011112
Classification : 05C85,  68505
Mots clés : algorithms, bipartite graphs, biclique-Helly, biclique matrices, clique matrices, Helly property, hypergraphs
@article{RO_2011__45_3_209_0,
author = {Groshaus, Marina and Szwarcfiter, Jayme Luis},
title = {Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {209--222},
publisher = {EDP-Sciences},
volume = {45},
number = {3},
year = {2011},
doi = {10.1051/ro/2011112},
zbl = {1247.05239},
mrnumber = {2865233},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2011112/}
}
Groshaus, Marina; Szwarcfiter, Jayme Luis. Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 45 (2011) no. 3, pp. 209-222. doi : 10.1051/ro/2011112. http://www.numdam.org/articles/10.1051/ro/2011112/

[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. | MR 1636476 | 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. | MR 2141223 | Zbl 1076.68048

[4] F. Gavril, Algorithms on circular-arc graphs. Networks 4 (1974) 357-369. | MR 376439 | 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. | MR 175811 | Zbl 0121.26003

[6] M. Groshaus and J.L. Szwarcfiter, Biclique-Helly graphs. Graphs Combin. 23 (2007) 633-645. | MR 2365416 | 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. | MR 2383735 | Zbl 1153.05059

[8] M. Groshaus and J.L. Szwarcfiter, Biclique graphs and biclique matrices. J. Graph Theory 63 (2010) 1-16. | MR 2590322 | 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 Mathematics 282 (2004) 193-208. | MR 2059519 | Zbl 1042.05073

[10] Zs. Tuza, Covering of graphs by complete bipartite subgraphs: complexity of {0,1} matrices. Combinatorica 4 (1984) 111-116. | MR 739419 | Zbl 0559.05050