| Issue |
RAIRO-Oper. Res.
Volume 45, Number 3, July-September 2011
|
|
|---|---|---|
| Page(s) | 209 - 222 | |
| DOI | https://doi.org/10.1051/ro/2011112 | |
| Published online | 24 October 2011 | |
Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs*,, **
1
Universidad de Buenos Aires, Departamento de
Computación, CONICET Buenos
Aires, Argentina
groshaus@dc.uba.ar
2
Universidade Federal do Rio de Janeiro,
IM, COPPE, and NCE,
Rio de Janeiro,
Brazil
jayme@nce.ufrj.br
Received:
15
May
2010
Accepted:
19
July
2011
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.
Mathematics Subject Classification: 05C85 / 68505
Key words: Algorithms / bipartite graphs / biclique-Helly / biclique matrices / clique matrices / Helly property / hypergraphs
© EDP Sciences, ROADEF, SMAI 2011
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.