Enumeration aspects of maximal cliques and bicliques
We present a general framework to study enumeration algorithms for maximal cliques and maximal bicliques of a graph. Given a graph G G , we introduce the notion of the transition graph T(G) T ( G ) whose vertices are maximal cliques of G G and arcs are transitions between cliques. We show that T(G) T ( G ) is a strongly connected graph and characterize a rooted cover tree of T(G) T ( G ) which appears implicitly in [D.S. Johnson, M. Yannakakis, C.H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters 27 (1988) 119123; S. Tsukiyama, M. Ide, M. Aiyoshi, I. Shirawaka, A new algorithm for generating all the independent sets, SIAM Journal on Computing 6 (1977) 505517]. When G G is a bipartite graph, we show that the Galois lattice of G G is a partial graph of T(G) T ( G ) and we deduce that algorithms based on the Galois lattice are a particular search of T(G) T ( G ) . Moreover, we show that algorithms in [G. Alexe, S. Alexe, Y. Crama, S. Foldes, P.L. Hammer, B. Simeone, Consensus algorithms for the generation of all maximal bicliques, Discrete Applied Mathematics 145 (1) (2004) 1121; L. Nourine, O. Raynaud, A fast algorithm for building lattices, Information Processing Letters 71 (1999) 199204] generate maximal bicliques of a bipartite graph in O(n2) O ( n 2 ) per maximal biclique, where n n is the number of vertices in G G . Finally, we show that under some specific numbering, the transition graph T(G) T ( G ) has a hamiltonian path for chordal and comparability graphs.
maximal cliques enumeration algorithms maximal bicliques lattice