Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time

DOI10.1007/978-3-642-17517-6_36zbMath1311.05187OpenAlexW1567562836MaRDI QIDQ3060751

Darren Strash, Maarten Löffler, David Eppstein

Publication date: 9 December 2010

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2011/2935/

zbMATH Keywords

fixed-parameter tractabilitysparse graphs\(d\)-degenerate graphsBron-Kerbosch algorithmmaximal clique listing algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (26)

Parallel Maximum Clique Algorithms with Applications to Network Analysis ⋮ A linear time algorithm for maximal clique enumeration in large sparse graphs ⋮ Local community detection based on small cliques ⋮ Building efficient and compact data structures for simplicial complexes ⋮ Facet-inducing inequalities and a cut-and-branch for the bandwidth coloring polytope based on the orientation model ⋮ Maximal independent sets in clique-free graphs ⋮ Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks ⋮ Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay ⋮ Refined pivot selection for maximal clique enumeration in graphs ⋮ Finding Cliques in Social Networks: A New Distribution-Free Model ⋮ Unnamed Item ⋮ Sparsity measure of a network graph: Gini index ⋮ A color-avoiding approach to subgraph counting in bounded expansion classes ⋮ Discovering the hidden community structure of public transportation networks ⋮ Detecting capital market convergence clubs ⋮ Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network ⋮ Testing One Hypothesis Multiple Times: The Multidimensional Case ⋮ Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs ⋮ Core Decomposition, Maintenance and Applications ⋮ A two-level graph partitioning problem arising in mobile wireless communications ⋮ Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Enumerating all maximal biclusters in numerical datasets ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ Exploiting the formation of maximal cliques in social networks

This page was built for publication: Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time