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

Abstract

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

How to cite

top

Groshaus, 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
  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.  
  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.  
  4. F. Gavril, Algorithms on circular-arc graphs. Networks4 (1974) 357–369.  
  5. P.C. Gilmore and A.J. Hoffman, A characterization of comparability graphs and of interval graphs. Canadian J. Math.16 (1964) 539–548.  
  6. M. Groshaus and J.L. Szwarcfiter, Biclique-Helly graphs. Graphs Combin.23 (2007) 633–645.  
  7. M. Groshaus and J.L. Szwarcfiter, On hereditary Helly classes of graphs. Discrete Math. Theor. Comput. Sci.10 (2008) 71–78.  
  8. M. Groshaus and J.L. Szwarcfiter, Biclique graphs and biclique matrices. J. Graph Theory63 (2010) 1–16.  
  9. 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.  
  10. Zs. Tuza, Covering of graphs by complete bipartite subgraphs: complexity of {0,1} matrices. Combinatorica4 (1984) 111–116. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.