Fast maximal cliques enumeration in sparse graphs

DOI10.1007/S00453-012-9632-8MaRDI QIDQ1949748zbMATH OpenOpenAlexFDO

Authors Lijun Chang, Jeffrey Xu Yu, Lu Qin

Publication date 16 May 2013

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-012-9632-8

zbMATH Keywords

\(H\)-partition\(H\)-valuemaximal cliquepolynomial delaysparse graph

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Algorithm Theory - SWAT 2004
• Enumerating maximal cliques in large sparse graphs
• Listing all maximal cliques in sparse graphs in near-optimal time
• Listing all maximal cliques in large sparse real-world graphs
• A linear time algorithm for maximal clique enumeration in large sparse graphs

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• Algorithm 457: finding all cliques of an undirected graph
• Algorithm Theory - SWAT 2004
• Arboricity and Subgraph Listing Algorithms
• Cluster-C, an algorithm for the large-scale clustering of protein sequences based on the extraction of maximal cliques
• On generating all maximal independent sets
• The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
• The worst-case time complexity for generating all maximal cliques and computational experiments

Cited in

(26)

• Efficiently enumerating all maximal cliques with bit-parallelism
• A new decomposition technique for maximal clique enumeration for sparse graphs
• An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
• Efficient enumeration of maximal induced bicliques
• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• Computing maximum \(k\)-defective cliques in massive graphs
• On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• Local search for diversified top-\(k\) clique search problem
• A linear time algorithm for maximal clique enumeration in large sparse graphs
• On Fast Enumeration of Pseudo Bicliques
• Listing all maximal cliques in sparse graphs in near-optimal time
• On CLIQUE Problem for Sparse Graphs of Large Dimension
• Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques
• Enumerating maximal cliques in large sparse graphs
• Solving maximum clique in sparse graphs: an \({O(nm+n2^{d/4})}\) algorithm for \(d\)-degenerate graphs
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• An output sensitive algorithm for maximal clique enumeration in sparse graphs
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• Algorithm Theory - SWAT 2004
• A linear delay algorithm for enumeration of 2-edge/vertex-connected induced subgraphs
• A linear delay algorithm of enumerating strongly-connected induced subgraphs based on SSD set system
• A linear delay algorithm in SD set system and its application to subgraph enumeration
• A linear-delay algorithm for enumerating strongly-connected induced subgraphs based on SSD set system
• An efficient algorithm for solving pseudo clique enumeration problem

Describes a project that uses

Uses Software

• Cluster-C
• Algorithm 457

This page was built for publication: Fast maximal cliques enumeration in sparse graphs

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