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

DOI10.4230/LIPICS.ICALP.2016.148MaRDI QIDQ4598291zbMATH OpenFDO

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

Publication date 19 December 2017

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2016.148

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)

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

Cited in

(22)

• 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
• On maximal cliques with connectivity constraints in directed 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
• On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• Efficient enumeration of dominating sets for sparse graphs
• Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
• Proximity Search for Maximal Subgraph Enumeration
• 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)