DIMACS TR: 2002-52
Consensus algorithms for the generation of all maximal bicliques
Authors: Gabriela Alexe, Sorin Alexe, Yves Crama, Stephan Foldes, Peter L. Hammer and Bruno Simeone
We describe a new algorithm for generating all maximal bicliques
(i.e. complete bipartite, not necessarily induced subgraphs) of a graph.
The algorithm is inspired by, and is quite similar to, the consensus
method used in propositional logic. We show that some variants of the
algorithm are totally polynomial, and even incrementally polynomial. The
total complexity of the most efficient variant of the algorithms presented
here is polynomial in the input size, and only linear in the output size.
Computational experiments demonstrate its high efficiency on randomly
generated graphs with up to 2,000 vertices and 20,000 edges.
Paper Available at:
DIMACS Home Page