Fast maximal cliques enumeration in sparse graphs
From MaRDI portal
Publication:1949748
DOI10.1007/s00453-012-9632-8zbMath1263.05045OpenAlexW1983365058MaRDI QIDQ1949748
Lu Qin, Lijun Chang, Jeffrey Xu Yu
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
Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (11)
Efficiently enumerating all maximal cliques with bit-parallelism ⋮ A linear delay algorithm for enumeration of 2-edge/vertex-connected induced subgraphs ⋮ Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms ⋮ Listing Maximal Independent Sets with Minimal Space and Bounded Delay ⋮ A new decomposition technique for maximal clique enumeration for sparse graphs ⋮ Efficient enumeration of maximal induced bicliques ⋮ Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs ⋮ Local search for diversified top-\(k\) clique search problem ⋮ An improved upper bound on maximal clique listing via rectangular fast matrix multiplication ⋮ Unnamed Item ⋮ On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
Uses Software
Cites Work
- The worst-case time complexity for generating all maximal cliques and computational experiments
- On generating all maximal independent sets
- Cluster-C, an algorithm for the large-scale clustering of protein sequences based on the extraction of maximal cliques
- The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
- Arboricity and Subgraph Listing Algorithms
- A New Algorithm for Generating All the Maximal Independent Sets
- Algorithm Theory - SWAT 2004
- Algorithm 457: finding all cliques of an undirected graph
This page was built for publication: Fast maximal cliques enumeration in sparse graphs