A new decomposition technique for maximal clique enumeration for sparse graphs

DOI10.1016/J.TCS.2018.10.014zbMath1421.68138OpenAlexW2897305385MaRDI QIDQ1740688

George Manoussakis

Publication date: 2 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.10.014

zbMATH Keywords

algorithmsenumerationcountingmaximal cliques\(k\)-degenerate graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms ⋮ A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number ⋮ On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms

Uses Software

• Algorithm 457

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
• The worst-case time complexity for generating all maximal cliques and computational experiments
• A note on the problem of reporting maximal cliques
• On generating all maximal independent sets
• An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
• On-line construction of suffix trees
• Fast maximal cliques enumeration in sparse graphs
• Exact Algorithms for Maximum Independent Set
• Extremal Combinatorics
• Emergence of Scaling in Random Networks
• Elimination graphs
• Bounded Arboricity to Determine the Local Structure of Sparse Graphs
• Arboricity and Subgraph Listing Algorithms
• A Space-Economical Suffix Tree Construction Algorithm
• A New Algorithm for Generating All the Maximal Independent Sets
• Algorithms on Strings, Trees and Sequences
• Reducibility among Combinatorial Problems
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• On Independent Sets and Bicliques in Graphs
• Algorithm Theory - SWAT 2004
• k-Degenerate Graphs
• Algorithm 457: finding all cliques of an undirected graph
• On cliques in graphs

This page was built for publication: A new decomposition technique for maximal clique enumeration for sparse graphs