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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :