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]](https://bibbase.org/img/filetypes/link.svg "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
{"_id":"wiSvPgmjK2RnQZMBx","authorIDs":[],"author_short":["Gély, A.","Nourine, L.","Sadi, B."],"bibbaseid":"gly-nourine-sadi-enumerationaspectsofmaximalcliquesandbicliques-2009","bibdata":{"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","Nourine, Lhouari","Sadi, Bachir"],"author_short":["Gély, A.","Nourine, L.","Sadi, B."],"bibtex":"@article{ Gely2009,\n 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.},\n author = {Gély, Alain and Nourine, Lhouari and Sadi, Bachir},\n doi = {10.1016/j.dam.2008.10.010},\n file = {:Users/KunihiroWASA/Dropbox/paper/2009/Gély, Nourine, Sadi, Enumeration aspects of maximal cliques and bicliques, 2009.pdf:pdf},\n issn = {0166218X},\n journal = {Discrete Applied Mathematics},\n keywords = {Enumeration algorithms,Lattice,Maximal bicliques,Maximal cliques},\n month = {April},\n number = {7},\n pages = {1447--1459},\n title = {{Enumeration aspects of maximal cliques and bicliques}},\n url = {http://www.sciencedirect.com/science/article/pii/S0166218X08004563 http://linkinghub.elsevier.com/retrieve/pii/S0166218X08004563},\n volume = {157},\n year = {2009}\n}","bibtype":"article","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","id":"Gely2009","issn":"0166218X","journal":"Discrete Applied Mathematics","key":"Gely2009","keywords":"Enumeration algorithms,Lattice,Maximal bicliques,Maximal cliques","month":"April","number":"7","pages":"1447--1459","title":"Enumeration aspects of maximal cliques and bicliques","type":"article","url":"http://www.sciencedirect.com/science/article/pii/S0166218X08004563 http://linkinghub.elsevier.com/retrieve/pii/S0166218X08004563","volume":"157","year":"2009","bibbaseid":"gly-nourine-sadi-enumerationaspectsofmaximalcliquesandbicliques-2009","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/S0166218X08004563 http://linkinghub.elsevier.com/retrieve/pii/S0166218X08004563"},"keyword":["Enumeration algorithms","Lattice","Maximal bicliques","Maximal cliques"],"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:44.103Z","downloads":0,"keywords":["enumeration algorithms","lattice","maximal bicliques","maximal cliques"],"search_terms":["enumeration","aspects","maximal","cliques","bicliques","gély","nourine","sadi"],"title":"Enumeration aspects of maximal cliques and bicliques","year":2009,"dataSources":["YRMeqhMHoNu9HzJoC"]}