Efficiently enumerating all maximal cliques with bit-parallelism
From MaRDI portal
Publication:1651581
DOI10.1016/j.cor.2017.12.006zbMath1392.68333arXiv1801.00202OpenAlexW2775591332MaRDI QIDQ1651581
Pablo San Segundo, Jorge Artieda, Darren Strash
Publication date: 12 July 2018
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1801.00202
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) 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
Overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms ⋮ Preprocessing and cutting planes with conflict graphs ⋮ On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms ⋮ GreedyBB
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An exact bit-parallel algorithm for the maximum clique problem
- An algorithm for reporting maximal \(c\)-cliques
- The worst-case time complexity for generating all maximal cliques and computational experiments
- An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- Refined pivot selection for maximal clique enumeration in graphs
- An exact algorithm for the maximum clique problem
- A note on the problem of reporting maximal cliques
- Enumerating all connected maximal common subgraphs in two graphs
- Reverse search for enumeration
- An improved bit parallel exact maximum clique algorithm
- Fast maximal cliques enumeration in sparse graphs
- A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
- Arboricity and Subgraph Listing Algorithms
- Smallest-last ordering and clustering and graph coloring algorithms
- A Sufficient Condition for Backtrack-Free Search
- A New Algorithm for Generating All the Maximal Independent Sets
- Cliques of a graph-variations on the Bron-Kerbosch algorithm
- Reducibility among Combinatorial Problems
- Listing All Maximal Cliques in Large Sparse Real-World Graphs
- Algorithm Theory - SWAT 2004
- An upper bound for the chromatic number of a graph and its application to timetabling problems
- k-Degenerate Graphs
- An Analysis of Some Graph Theoretical Cluster Techniques
- Algorithm 457: finding all cliques of an undirected graph
- On cliques in graphs