Reference : Consensus algorithms for the generation of all maximal bicliques
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/1729
Consensus algorithms for the generation of all maximal bicliques
English
Alexe, Gabriela [> > > >]
Alexe, Sorin [> > > >]
Crama, Yves mailto [Université de Liège - ULg > HEC - Ecole de gestion de l'ULg > Recherche opérationnelle et gestion de la production >]
Foldes, Stephan [Tampere University of Technology > Department of Mathematics]
Hammer, Peter L. [> > > >]
Simeone, Bruno [> > > >]
30-Dec-2004
Discrete Applied Mathematics
Elsevier Science Bv
145
1 Sp. Iss. SI
11-21
Yes (verified by ORBi)
International
0166-218X
Amsterdam
[en] maximal complete bipartite subgraph ; biclique ; consensus-type algorithm ; algorithmic graph theory ; incremental polynomial enumeration
[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.
Researchers
http://hdl.handle.net/2268/1729
10.1016/j.dam.2003.09.004
Available online at www.sciencedirect.com

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
Bicliques.pdfNo commentaryAuthor preprint980.93 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.