363(1):28-42.

Paper doi abstract bibtex

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