Listing all maximal cliques in sparse graphs in near-optimal time

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

Cited In (32)

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

   Recommendations

Listing All Maximal Cliques in Large Sparse Real-World Graphs 👍 👎
Title not available (Why is that?) 👍 👎
A new decomposition technique for maximal clique enumeration for sparse graphs 👍 👎
Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs 👍 👎
Fast maximal cliques enumeration in sparse graphs 👍 👎

This page was built for publication: Listing all maximal cliques in sparse graphs in near-optimal time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3060751)