Article (Scientific journals)
Consensus algorithms for the generation of all maximal bicliques
Alexe, Gabriela; Alexe, Sorin; Crama, Yves et al.
2004In Discrete Applied Mathematics, 145 (1 Sp. Iss. SI), p. 11-21
Peer Reviewed verified by ORBi
 

Files


Full Text
Bicliques.pdf
Author preprint (1 MB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
maximal complete bipartite subgraph; biclique; consensus-type algorithm; algorithmic graph theory; incremental polynomial enumeration
Abstract :
[en] 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 2000 vertices and 20,000 edges. (C) 2003 Elsevier B.V. All rights reserved.
Disciplines :
Mathematics
Author, co-author :
Alexe, Gabriela
Alexe, Sorin
Crama, Yves  ;  Université de Liège - ULiège > HEC - École de gestion de l'ULiège > Recherche opérationnelle et gestion de la production
Foldes, Stephan;  Tampere University of Technology > Department of Mathematics
Hammer, Peter L.
Simeone, Bruno
Language :
English
Title :
Consensus algorithms for the generation of all maximal bicliques
Publication date :
30 December 2004
Journal title :
Discrete Applied Mathematics
ISSN :
0166-218X
eISSN :
1872-6771
Publisher :
Elsevier Science Bv, Amsterdam, Netherlands
Volume :
145
Issue :
1 Sp. Iss. SI
Pages :
11-21
Peer reviewed :
Peer Reviewed verified by ORBi
Commentary :
Available online at www.sciencedirect.com
Available on ORBi :
since 02 December 2008

Statistics


Number of views
158 (7 by ULiège)
Number of downloads
747 (3 by ULiège)

Scopus citations®
 
126
Scopus citations®
without self-citations
119
OpenCitations
 
107

Bibliography


Similar publications



Contact ORBi