2000-14: Consensus Algorithms for the Generation of all Maximal Bicliques

DIMACS TR: 2000-14

Consensus Algorithms for the Generation of all Maximal Biclique s

Authors: Gabriela Alexe, Sorin Alexe, Stephan Foldes, Peter L. Hammer and Bruno Simeone

ABSTRACT
We describe a consensus-type algorithm for determining all the maximal complete bipartite (not necessarily induced) subgraphs of a graph. We show that by imposing a particular order in which the consensus type operations should be executed, this algorithm becomes totally polynomial. By imposing a further restriction on the way the algorithm has to be executed, we derive an improved variant of it, the complexity of which is bounded by a polynomial that is cubic in the input size, and only linear in the output size, and show its high efficiency on numerous computational experiments on randomly generated graphs with up to 1000 vertices and 6000 edges.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-14.ps.gz

Revision as DIMACS TR 2002-52 Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2002-52.ps.gz

DIMACS Home Page