The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments. Tomita, E., Tanaka, A., & Takahashi, H. 363(1):28-42. Paper doi abstract bibtex We present a depth-first search algorithm for generating all maximal cliques of an undirected graph, in which pruning methods are employed as in the Bron–Kerbosch algorithm. All the maximal cliques generated are output in a tree-like form. Subsequently, we prove that its worst-case time complexity is O(3n/3) for an n-vertex graph. This is optimal as a function of n, since there exist up to 3n/3 maximal cliques in an n-vertex graph. The algorithm is also demonstrated to run very fast in practice by computational experiments.
@article{tomitaWorstcaseTimeComplexity2006,
title = {The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments},
volume = {363},
issn = {0304-3975},
url = {http://www.sciencedirect.com/science/article/pii/S0304397506003586},
doi = {10.1016/j.tcs.2006.06.015},
abstract = {We present a depth-first search algorithm for generating all maximal cliques of an undirected graph, in which pruning methods are employed as in the Bron–Kerbosch algorithm. All the maximal cliques generated are output in a tree-like form. Subsequently, we prove that its worst-case time complexity is O(3n/3) for an n-vertex graph. This is optimal as a function of n, since there exist up to 3n/3 maximal cliques in an n-vertex graph. The algorithm is also demonstrated to run very fast in practice by computational experiments.},
number = {1},
journaltitle = {Theoretical Computer Science},
shortjournal = {Theoretical Computer Science},
series = {Computing and {{Combinatorics}}},
urldate = {2018-07-31},
date = {2006-10-25},
pages = {28-42},
keywords = {Computational experiments,Enumeration,Maximal cliques,Worst-case time complexity},
author = {Tomita, Etsuji and Tanaka, Akira and Takahashi, Haruhisa},
file = {/home/dimitri/Nextcloud/Zotero/storage/QDLTAXHX/Tomita et al. - 2006 - The worst-case time complexity for generating all .pdf;/home/dimitri/Nextcloud/Zotero/storage/TCJ8J7MV/S0304397506003586.html}
}
Downloads: 0
{"_id":"gSRRFhPoeF5CMBzQP","bibbaseid":"tomita-tanaka-takahashi-theworstcasetimecomplexityforgeneratingallmaximalcliquesandcomputationalexperiments","authorIDs":[],"author_short":["Tomita, E.","Tanaka, A.","Takahashi, H."],"bibdata":{"bibtype":"article","type":"article","title":"The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments","volume":"363","issn":"0304-3975","url":"http://www.sciencedirect.com/science/article/pii/S0304397506003586","doi":"10.1016/j.tcs.2006.06.015","abstract":"We present a depth-first search algorithm for generating all maximal cliques of an undirected graph, in which pruning methods are employed as in the Bron–Kerbosch algorithm. All the maximal cliques generated are output in a tree-like form. Subsequently, we prove that its worst-case time complexity is O(3n/3) for an n-vertex graph. This is optimal as a function of n, since there exist up to 3n/3 maximal cliques in an n-vertex graph. The algorithm is also demonstrated to run very fast in practice by computational experiments.","number":"1","journaltitle":"Theoretical Computer Science","shortjournal":"Theoretical Computer Science","series":"Computing and Combinatorics","urldate":"2018-07-31","date":"2006-10-25","pages":"28-42","keywords":"Computational experiments,Enumeration,Maximal cliques,Worst-case time complexity","author":[{"propositions":[],"lastnames":["Tomita"],"firstnames":["Etsuji"],"suffixes":[]},{"propositions":[],"lastnames":["Tanaka"],"firstnames":["Akira"],"suffixes":[]},{"propositions":[],"lastnames":["Takahashi"],"firstnames":["Haruhisa"],"suffixes":[]}],"file":"/home/dimitri/Nextcloud/Zotero/storage/QDLTAXHX/Tomita et al. - 2006 - The worst-case time complexity for generating all .pdf;/home/dimitri/Nextcloud/Zotero/storage/TCJ8J7MV/S0304397506003586.html","bibtex":"@article{tomitaWorstcaseTimeComplexity2006,\n title = {The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments},\n volume = {363},\n issn = {0304-3975},\n url = {http://www.sciencedirect.com/science/article/pii/S0304397506003586},\n doi = {10.1016/j.tcs.2006.06.015},\n abstract = {We present a depth-first search algorithm for generating all maximal cliques of an undirected graph, in which pruning methods are employed as in the Bron–Kerbosch algorithm. All the maximal cliques generated are output in a tree-like form. Subsequently, we prove that its worst-case time complexity is O(3n/3) for an n-vertex graph. This is optimal as a function of n, since there exist up to 3n/3 maximal cliques in an n-vertex graph. The algorithm is also demonstrated to run very fast in practice by computational experiments.},\n number = {1},\n journaltitle = {Theoretical Computer Science},\n shortjournal = {Theoretical Computer Science},\n series = {Computing and {{Combinatorics}}},\n urldate = {2018-07-31},\n date = {2006-10-25},\n pages = {28-42},\n keywords = {Computational experiments,Enumeration,Maximal cliques,Worst-case time complexity},\n author = {Tomita, Etsuji and Tanaka, Akira and Takahashi, Haruhisa},\n file = {/home/dimitri/Nextcloud/Zotero/storage/QDLTAXHX/Tomita et al. - 2006 - The worst-case time complexity for generating all .pdf;/home/dimitri/Nextcloud/Zotero/storage/TCJ8J7MV/S0304397506003586.html}\n}\n\n","author_short":["Tomita, E.","Tanaka, A.","Takahashi, H."],"key":"tomitaWorstcaseTimeComplexity2006","id":"tomitaWorstcaseTimeComplexity2006","bibbaseid":"tomita-tanaka-takahashi-theworstcasetimecomplexityforgeneratingallmaximalcliquesandcomputationalexperiments","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/S0304397506003586"},"keyword":["Computational experiments","Enumeration","Maximal cliques","Worst-case time complexity"],"downloads":0},"bibtype":"article","biburl":"https://raw.githubusercontent.com/dlozeve/newblog/master/bib/all.bib","creationDate":"2020-01-08T20:39:39.162Z","downloads":0,"keywords":["computational experiments","enumeration","maximal cliques","worst-case time complexity"],"search_terms":["worst","case","time","complexity","generating","maximal","cliques","computational","experiments","tomita","tanaka","takahashi"],"title":"The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments","year":null,"dataSources":["3XqdvqRE7zuX4cm8m"]}