# Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs*, **

Marina Groshaus; Jayme Luis Szwarcfiter

RAIRO - Operations Research (2011)

- Volume: 45, Issue: 3, page 209-222
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topGroshaus, Marina, and Szwarcfiter, Jayme Luis. "Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs*, **." RAIRO - Operations Research 45.3 (2011): 209-222. <http://eudml.org/doc/276361>.

@article{Groshaus2011,

abstract = {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.},

author = {Groshaus, Marina, Szwarcfiter, Jayme Luis},

journal = {RAIRO - Operations Research},

keywords = {Algorithms; bipartite graphs; biclique-Helly; biclique matrices; clique matrices; Helly property; hypergraphs; algorithms},

language = {eng},

month = {10},

number = {3},

pages = {209-222},

publisher = {EDP Sciences},

title = {Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs*, **},

url = {http://eudml.org/doc/276361},

volume = {45},

year = {2011},

}

TY - JOUR

AU - Groshaus, Marina

AU - Szwarcfiter, Jayme Luis

TI - Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs*, **

JO - RAIRO - Operations Research

DA - 2011/10//

PB - EDP Sciences

VL - 45

IS - 3

SP - 209

EP - 222

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

LA - eng

KW - Algorithms; bipartite graphs; biclique-Helly; biclique matrices; clique matrices; Helly property; hypergraphs; algorithms

UR - http://eudml.org/doc/276361

ER -

## References

top- 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
- C. Berge, Hypergraphs. Elsevier Science Publishers (1989).
- 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
- F. Gavril, Algorithms on circular-arc graphs. Networks4 (1974) 357–369. Zbl0309.05126
- 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
- M. Groshaus and J.L. Szwarcfiter, Biclique-Helly graphs. Graphs Combin.23 (2007) 633–645. Zbl1140.05314
- M. Groshaus and J.L. Szwarcfiter, On hereditary Helly classes of graphs. Discrete Math. Theor. Comput. Sci.10 (2008) 71–78. Zbl1153.05059
- M. Groshaus and J.L. Szwarcfiter, Biclique graphs and biclique matrices. J. Graph Theory63 (2010) 1–16. Zbl1216.05104
- 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
- Zs. Tuza, Covering of graphs by complete bipartite subgraphs: complexity of {0,1} matrices. Combinatorica4 (1984) 111–116. Zbl0559.05050

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.