Efficiently enumerating all maximal cliques with bit-parallelism

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

zbMATH Keywords

combinatorial optimizationbranch-and-boundmaximal cliquesubgraph enumerationbitstring

Mathematics Subject Classification ID

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

• BHOSLIB
• DIMACS
• GitHub
• Algorithm 457

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