Listing All Maximal Cliques in Large Sparse Real-World Graphs
From MaRDI portal
Publication:5266538
DOI10.1145/2543629zbMath1365.05276arXiv1103.0318OpenAlexW1485742133WikidataQ56210402 ScholiaQ56210402MaRDI QIDQ5266538
Maarten Löffler, Darren Strash, David Eppstein
Publication date: 16 June 2017
Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1103.0318
Analysis of algorithms (68W40) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Parallel Maximum Clique Algorithms with Applications to Network Analysis ⋮ Proximity Search for Maximal Subgraph Enumeration ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs ⋮ Efficiently enumerating all maximal cliques with bit-parallelism ⋮ Local community detection based on small cliques ⋮ A MILP model and two heuristics for the bin packing problem with conflicts and item fragmentation ⋮ Essentially tight kernels for (weakly) closed graphs ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ Computing maximal cliques in link streams ⋮ Finding Cliques in Social Networks: A New Distribution-Free Model ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Enumerating maximal cliques in link streams with durations ⋮ Unnamed Item ⋮ Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications ⋮ Constraint and Satisfiability Reasoning for Graph Coloring ⋮ SIAS-miner: mining subjectively interesting attributed subgraphs ⋮ Listing Maximal Subgraphs Satisfying Strongly Accessible Properties ⋮ A Constructive Arboricity Approximation Scheme ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Listing Maximal Independent Sets with Minimal Space and Bounded Delay ⋮ A new decomposition technique for maximal clique enumeration for sparse graphs ⋮ Maximal strongly connected cliques in directed graphs: algorithms and bounds ⋮ Efficient enumeration of dominating sets for sparse graphs ⋮ Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph ⋮ Sublinear-space and bounded-delay algorithms for maximal clique enumeration in graphs ⋮ Fast circular arc segmentation based on approximate circularity and cuboid graph ⋮ Unnamed Item ⋮ An improved upper bound on maximal clique listing via rectangular fast matrix multiplication ⋮ Faster algorithms for counting subgraphs in sparse graphs ⋮ Unnamed Item ⋮ Declawing a graph: polyhedra and branch-and-cut algorithms ⋮ Compact structure for sparse undirected graphs based on a clique graph partition ⋮ Improved Space Efficient Algorithms for BFS, DFS and Applications ⋮ On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms ⋮ Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection ⋮ Unnamed Item ⋮ Space efficient linear time algorithms for BFS, DFS and applications ⋮ 1-planarity testing and embedding: an experimental study ⋮ Worst-case analysis of clique MIPs ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
