Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques

DOI10.4230/LIPICS.ICALP.2016.148zbMATH Open1388.68218MaRDI QIDQ4598291FDOQ4598291

Authors: Alessio Conte, Roberto Grossi, Andrea Marino, Luca Versari 

Publication date: 19 December 2017

Recommendations

• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• Parallel Algorithm for Enumerating Maximal Cliques in Complex Network
• Fast maximal cliques enumeration in sparse graphs
• A linear time algorithm for maximal clique enumeration in large sparse graphs
• Algorithm Theory - SWAT 2004

zbMATH Keywords

maximal cliquesenumeration algorithmsspace efficiencyreverse searchnetwork mining and analytics

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Cited In (22)

• On maximal cliques with connectivity constraints in directed graphs
• Maximal strongly connected cliques in directed graphs: algorithms and bounds
• Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph
• Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs
• An improved upper bound on maximal clique listing via rectangular fast matrix multiplication
• Large-scale clique cover of real-world networks
• Polynomial-delay generation of functional digraphs up to isomorphism
• Efficient enumeration of graph orientations with sources
• A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
• Listing Maximal Subgraphs Satisfying Strongly Accessible Properties
• A fast discovery algorithm for large common connected induced subgraphs
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Efficient enumeration of dominating sets for sparse graphs
• Efficient enumeration of dominating sets for sparse graphs
• On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• Proximity Search for Maximal Subgraph Enumeration
• Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• Efficient enumeration of maximal induced bicliques
• A new decomposition technique for maximal clique enumeration for sparse graphs
• Efficiently enumerating all maximal cliques with bit-parallelism
• An output sensitive algorithm for maximal clique enumeration in sparse graphs
• Polynomial-delay and polynomial-space enumeration of large maximal matchings

This page was built for publication: Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques

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