Enumeration aspects of maximal cliques and bicliques. Gély, A., Nourine, L., & Sadi, B. Discrete Applied Mathematics, 157(7):1447--1459, April, 2009.
Enumeration aspects of maximal cliques and bicliques [link]Paper  doi  abstract   bibtex   
We present a general framework to study enumeration algorithms for maximal cliques and maximal bicliques of a graph. Given a graph G, we introduce the notion of the transition graph T(G) whose vertices are maximal cliques of G and arcs are transitions between cliques. We show that T(G) is a strongly connected graph and characterize a rooted cover tree of 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) 119–123; S. Tsukiyama, M. Ide, M. Aiyoshi, I. Shirawaka, A new algorithm for generating all the independent sets, SIAM Journal on Computing 6 (1977) 505–517]. When G is a bipartite graph, we show that the Galois lattice of G is a partial graph of T(G) and we deduce that algorithms based on the Galois lattice are a particular search of 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) 11–21; L. Nourine, O. Raynaud, A fast algorithm for building lattices, Information Processing Letters 71 (1999) 199–204] generate maximal bicliques of a bipartite graph in O(n2) per maximal biclique, where n is the number of vertices in G. Finally, we show that under some specific numbering, the transition graph T(G) has a hamiltonian path for chordal and comparability graphs.
@article{ Gely2009,
  abstract = {We present a general framework to study enumeration algorithms for maximal cliques and maximal bicliques of a graph. Given a graph G, we introduce the notion of the transition graph T(G) whose vertices are maximal cliques of G and arcs are transitions between cliques. We show that T(G) is a strongly connected graph and characterize a rooted cover tree of 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) 119–123; S. Tsukiyama, M. Ide, M. Aiyoshi, I. Shirawaka, A new algorithm for generating all the independent sets, SIAM Journal on Computing 6 (1977) 505–517]. When G is a bipartite graph, we show that the Galois lattice of G is a partial graph of T(G) and we deduce that algorithms based on the Galois lattice are a particular search of 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) 11–21; L. Nourine, O. Raynaud, A fast algorithm for building lattices, Information Processing Letters 71 (1999) 199–204] generate maximal bicliques of a bipartite graph in O(n2) per maximal biclique, where n is the number of vertices in G. Finally, we show that under some specific numbering, the transition graph T(G) has a hamiltonian path for chordal and comparability graphs.},
  author = {Gély, Alain and Nourine, Lhouari and Sadi, Bachir},
  doi = {10.1016/j.dam.2008.10.010},
  file = {:Users/KunihiroWASA/Dropbox/paper/2009/Gély, Nourine, Sadi, Enumeration aspects of maximal cliques and bicliques, 2009.pdf:pdf},
  issn = {0166218X},
  journal = {Discrete Applied Mathematics},
  keywords = {Enumeration algorithms,Lattice,Maximal bicliques,Maximal cliques},
  month = {April},
  number = {7},
  pages = {1447--1459},
  title = {{Enumeration aspects of maximal cliques and bicliques}},
  url = {http://www.sciencedirect.com/science/article/pii/S0166218X08004563 http://linkinghub.elsevier.com/retrieve/pii/S0166218X08004563},
  volume = {157},
  year = {2009}
}

Downloads: 0