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

DOI10.1007/978-3-642-17517-6_36zbMATH Open1311.05187OpenAlexW1567562836MaRDI QIDQ3060751FDOQ3060751

Authors: David Eppstein, Maarten Löffler, Darren Strash 

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/

Recommendations

• Listing all maximal cliques in large sparse real-world graphs
• An output sensitive algorithm for maximal clique enumeration in sparse graphs
• 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

zbMATH Keywords

sparse graphsfixed-parameter tractability\(d\)-degenerate graphsBron-Kerbosch algorithmmaximal clique listing algorithms

Mathematics Subject Classification ID

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 (41)

• 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
• An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
• 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
• Exploiting the formation of maximal cliques in social networks
• Parallel maximum clique algorithms with applications to network analysis
• A two-level graph partitioning problem arising in mobile wireless communications
• Building efficient and compact data structures for simplicial complexes
• A note on the problem of reporting maximal cliques
• 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
• Finding cliques in social networks: a new distribution-free model
• Maximal independent sets in clique-free graphs
• Local community detection based on small cliques
• Refined pivot selection for maximal clique enumeration in graphs
• Sublinear time estimation of degree distribution moments: the arboricity connection
• Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
• Computing and Combinatorics
• Listing all fixed-length simple cycles in sparse graphs in optimal time
• The worst-case time complexity for generating all maximal cliques and computational experiments
• 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
• Listing all maximal cliques in large sparse real-world graphs
• Facet-inducing inequalities and a cut-and-branch for the bandwidth coloring polytope based on the orientation model
• Efficient enumeration of maximal \(k\)-degenerate subgraphs in a chordal graph
• Why is maximum clique often easy in practice?
• A new decomposition technique for maximal clique enumeration for sparse graphs
• Title not available (Why is that?)
• An output sensitive algorithm for maximal clique enumeration in sparse graphs
• Fast maximal cliques enumeration in sparse graphs
• Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay
• Core decomposition, maintenance and applications
• Sparsity measure of a network graph: Gini index
• On the parameterized complexity of non-hereditary relaxations of clique

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)