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 : 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},
     mrnumber = {2865233},
     zbl = {1247.05239},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2011112/}
}
TY  - JOUR
AU  - Groshaus, Marina
AU  - Szwarcfiter, Jayme Luis
TI  - Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2011
SP  - 209
EP  - 222
VL  - 45
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2011112/
DO  - 10.1051/ro/2011112
LA  - en
ID  - RO_2011__45_3_209_0
ER  - 
%0 Journal Article
%A Groshaus, Marina
%A Szwarcfiter, Jayme Luis
%T Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2011
%P 209-222
%V 45
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2011112/
%R 10.1051/ro/2011112
%G en
%F RO_2011__45_3_209_0
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 | Zbl

[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 | Zbl

[4] F. Gavril, Algorithms on circular-arc graphs. Networks 4 (1974) 357-369. | MR | Zbl

[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 | Zbl

[6] M. Groshaus and J.L. Szwarcfiter, Biclique-Helly graphs. Graphs Combin. 23 (2007) 633-645. | MR | Zbl

[7] M. Groshaus and J.L. Szwarcfiter, On hereditary Helly classes of graphs. Discrete Math. Theor. Comput. Sci. 10 (2008) 71-78. | MR | Zbl

[8] M. Groshaus and J.L. Szwarcfiter, Biclique graphs and biclique matrices. J. Graph Theory 63 (2010) 1-16. | MR | Zbl

[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 | Zbl

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

Cité par Sources :