Consensus algorithms for the generation of all maximal bicliques

Alexe, Gabriela; Alexe, Sorin; Crama, Yves; Foldes, Stephan; Hammer, Peter L.; Simeone, Bruno

doi:10.1016/j.dam.2003.09.004

Download

Article (Scientific journals)

Consensus algorithms for the generation of all maximal bicliques

Alexe, Gabriela; Alexe, Sorin; Crama, Yves et al.

2004 • In Discrete Applied Mathematics, 145 (1 Sp. Iss. SI), p. 11-21

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/1729

DOI
10.1016/j.dam.2003.09.004

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

Bicliques.pdf

Author preprint (1 MB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

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

179 (7 by ULiège)

Number of downloads

772 (3 by ULiège)

More statistics

Scopus citations^®

134

Scopus citations^®
without self-citations

127

OpenCitations

107

OpenAlex citations

188

Bibliography

Agarwal, P., Alon, N., Aronov, B., Suri, S., Can visibility graphs be represented compactly? (1993) Proceedings of the Ninth ACM Symposium on Computational Geometry, pp. 338-347
Aho, A.V., Hopcroft, J.E., Ullman, J.D., (1974) The Design and Analysis of Computer Algorithms, , Reading: Addison-Wesley Publishing Company
Benzaken, Cl., Boyd, S., Hammer, P.L., Simeone, B., Adjoints of pure bidirected graphs (1983) Congress. Numer., 39, pp. 123-144
Benzaken, Cl., Hammer, P.L., Simeone, B., Some remarks on conflict graphs of quadratic pseudo-Boolean functions (1980) Internat. Ser. Numer. Math., 55, pp. 9-30
Bermond, J.-C., (1978) Couvertures des Arrêtes d'un Graphe par des Graphes Bipartis Complets, , Preprint, Univ. De Paris Sud, Centre d'Orsay, Rapport de Recherche No. 10
Blake, A., (1937) Canonical Expressions in Boolean Algebra, , Ph. D. Thesis, University of Chicago
Boros, E., Crama, Y., Hammer, P.L., Polynomial-time inference of all valid implications for Horn and related formulae (1990) Ann. Math. Artif. Intell., 1, pp. 21-32
Bylka, S., Idzik, A., Komar, J., Bipartite subgraphs of graphs with maximum degree three (1999) Graphs Combin., 15, pp. 129-136
Chang, C.L., Lee, R.C., (1973) Symbolic Logic and Mechanical Theorem Proving, , New York, San Francisco, London: Academic Press
Chung, F.R.K., On the coverings of graphs (1980) Discrete Math., 30, pp. 89-93
Chung, F.R.K., On the decomposition of graphs (1981) SIAM J. Algebraic Discrete Methods, 2, pp. 1-12
Chung, F.R.K., Erdös, P., Spencer, J., On the decomposition of graphs into complete bipartite subgraphs (1983) Stud. Pure Math., pp. 95-101
Crama, Y., Hammer, P.L., Recognition of quadratic graphs and adjoints of bidirected graphs (1989) Ann. New York Acad. Sci., 555, pp. 140-149
Dawande, M., Keskinocak, P., Swaminathan, J., Tayur, S., On the biclique and multi-partite clique problems (2001) J. Algorithms, 41 (2), pp. 388-403
Doherty, F.C.C., Lundgren, J.R., Siewert, D.J., Biclique covers and partitions of bipartite graphs and digraphs and related matrix ranks of {0,1} -matrices (1999) Congress. Numer., 136, pp. 73-96
Dulmage, A.L., Mendelsohn, N.S., Coverings of bipartite graphs (1958) Canad. J. Math., 10, pp. 517-534
Ebenegger, Ch., Hammer, P.L., De Werra, D., Pseudo-Boolean functions and stability of graphs (1984) Ann. Discrete Math., 19, pp. 83-97
Eppstein, D., Arboricity and bipartite subgraph listing algorithms (1994) Inform. Process. Lett., 51, pp. 207-211
Foldes, S., Hammer, P.L., Disjunctive and conjunctive normal forms of pseudo-Boolean functions (2000) Discrete Appl. Math., 107, pp. 1-26
Garey, M.R., Johnson, D.S., (1979) Computers and Intractability, A Guide to the Theory of NP-completeness, , San Francisco: Freeman
Glover, F., Maximum matching in a convex bipartite graph (1967) Naval Res. Logistics Q., 14, pp. 313-316
Golumbic, M.C., Hammer, P.L., Stability in circular arc graphs (1988) J. Algorithms, 9, pp. 314-320
Haemers, W.H., Bicliques and eigenvalues (1999) Research Memorandum, FEW 783. , Tilburg University
Hammer, P.L., The conflict graph of a pseudo-Boolean function (1978) Technical Report, , Bell Laboratories, West Long Branch, NJ
Hammer, P.L., Mahadev, N.V.R., De Werra, D., The struction of a graph: Application to CN-free graphs (1985) Combinatorica, 5, pp. 141-147
Hammer, P.L., Mahadev, N.V.R., De Werra, D., Stability in CAN-free graphs (1985) J. Combin. Theory Ser. B, 38, pp. 23-30
Hammer, P.L., Simeone, B., Quasimonotone Boolean functions and bistellar graphs (1980) Ann. Discrete Math., 9, pp. 107-119
Hochbaum, D.S., Approximating clique and biclique problems (1998) J. Algorithms, 29, pp. 174-200
Johnson, D.S., The NP-completeness column: An ongoing guide (1987) J. Algorithms, 8, pp. 438-448
Johnson, D.S., Yannakakis, M., Papadimitriou, C.H., On generating all maximal independent sets (1988) Inform. Process. Lett., 27, pp. 119-123
Kaufmann, A., Pichat, E., Méthodes mathématiques non numériques et leurs algorithmes (1977) Algorithmes de Recherche des Eléments Maximaux, 1. , Masson, Paris
Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R., Generating all maximal independent sets: NP-hardness and polynomial-time algorithms (1980) SIAM J. Comput., 9, pp. 558-565
Malgrange, Y., Recherche des sous-matrices premières d'une matrice à coefficients binaries, Applications à certains problèmes de graphe (1962) Deuxième Congrès de l'AFCALTI, pp. 231-242. , October 1962, Gauthier-Villars, Paris
Mehlhorn, K., (1984) Data Structures and Algorithms 2: Graph Algorithms and NP-Completeness, , Berlin: Springer
Papadimitriou, C.H., (1994) Computational Complexity, , Reading, MA: Addison-Wesley
Pasechnik, D.V., (1999) Bipartite Sandwiches: Bounding the Size of a Maximum Biclique, , preprint
Paull, M.C., Unger, S.H., Minimizing the number of states in incompletely specified sequential switching functions (1959) IRE Trans. Electron. Comput., EC-8, pp. 356-367
Peeters, R., The maximum edge biclique problem is NP-complete (2003) Discrete Appl. Math., 131, pp. 651-654
Pichat, E., The disangagement algorithm or a new generalization of the exclusion algorithm (1977) Discrete Math., 17, pp. 95-106
Quine, W., A way to simplify truth functions (1955) Amer. Math. Monthly, 62, pp. 627-631
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I., A new algorithm for generating all the maximal independent sets (1977) SIAM J. Comput., 6, pp. 505-517
Tuza, Z., Covering of graphs by complete bipartite subgraphs: Complexity of 0-1 matrices (1984) Combinatorica, 4, pp. 111-116
Yannakakis, M., Node- and edge-deletion NP-complete problems (1978) Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 253-264. , Association for Computing Machinery, New York