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.
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 :