The worst-case time complexity for generating all maximal cliques and computational experiments

2006/07/11 by Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Combinatorics #Complexity and Algorithms in Graphs #Computational complexity theory #Computer science #Discrete mathematics #Graph #Mathematics #Pruning #Running time #Time complexity #Undirected graph #Vertex (graph theory)

paper · pdf · doi:10.1016/j.tcs.2006.06.015

openalex publication_date 2006/07/11 · crossref created 2006/07/11 · crossref issued 2006/10/01 · crossref published 2006/10/01 · crossref published-print 2006/10/01 · crossref deposited 2025/10/05 · openalex created_date 2025/10/10 · crossref indexed 2026/07/21 · openalex updated_date 2026/08/01

Citations

• On cliques in graphs
• Arboricity and Subgraph Listing Algorithms
• Algorithms for maximum independent sets
• A New Algorithm for Generating All the Maximal Independent Sets
• Finding a Maximum Independent Set
• An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique
• Algorithm 457: finding all cliques of an undirected graph

Cited by

• An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique with Computational Experiments
• A note on the problem of reporting maximal cliques
• All maximal independent sets and dynamic dominance for sparse graphs
• Clique problem [wikipedia]
• Maximal independent set [wikipedia]