[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
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
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
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
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
