Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
DOI10.1007/S00453-019-00656-8zbMATH Open1433.68287OpenAlexW2995561890WikidataQ126548757 ScholiaQ126548757MaRDI QIDQ1987232FDOQ1987232
Authors: Alessio Conte, Roberto Grossi, Andrea Marino, Luca Versari 
Publication date: 14 April 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-019-00656-8
Recommendations
- Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques
- Fast maximal cliques enumeration in sparse graphs
- Algorithm Theory - SWAT 2004
- A linear time algorithm for maximal clique enumeration in large sparse graphs
- Parallel Algorithm for Enumerating Maximal Cliques in Complex Network
maximal cliquesenumeration algorithmsspace efficiencypolynomial-time delayreverse searchnetwork mining and analytics
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)
Cites Work
- Algorithm 457: finding all cliques of an undirected graph
- The complexity of computing the permanent
- A New Algorithm for Generating All the Maximal Independent Sets
- Color-coding
- Listing Triangles
- On cliques in graphs
- An efficient algorithm for solving pseudo clique enumeration problem
- Reverse search for enumeration
- The Enumeration of Maximal Cliques of Large Graphs
- A note on the problem of reporting maximal cliques
- On generating all maximal independent sets
- Arboricity and Subgraph Listing Algorithms
- The worst-case time complexity for generating all maximal cliques and computational experiments
- Algorithm Theory - SWAT 2004
- Fast maximal cliques enumeration in sparse graphs
- Listing all maximal cliques in sparse graphs in near-optimal time
- Enumeration aspects of maximal cliques and bicliques
- Corrections to Bierstone's Algorithm for Generating Cliques
- Enumeration Of Labelled Graphs
- A NOTE ON THE ENUMERATION AND LISTING OF ALL POSSIBLE TREES IN A CONNECTED LINEAR GRAPH
- Listing All Maximal Cliques in Large Sparse Real-World Graphs
- Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
- Title not available (Why is that?)
- An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
- Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph
- Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
- Listing Maximal Independent Sets with Minimal Space and Bounded Delay
Cited In (8)
- The complexity of dependency detection and discovery in relational databases
- Title not available (Why is that?)
- On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay
- A linear delay algorithm for enumeration of 2-edge/vertex-connected induced subgraphs
- On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
- Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
- On approximating the number of k-cliques in sublinear time
- Reconfiguration of cliques in a graph
Uses Software
This page was built for publication: Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1987232)
