A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
From MaRDI portal
Publication:3404446
DOI10.1007/978-3-642-11440-3_18zbMath1274.05455OpenAlexW1594785451MaRDI QIDQ3404446
Shinya Takahashi, Mitsuo Wakatsuki, Yoichi Sutani, Takanori Higashi, Etsuji Tomita
Publication date: 9 February 2010
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-11440-3_18
Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (40)
A review on algorithms for maximum clique problems ⋮ Scale reduction techniques for computing maximum induced bicliques ⋮ Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights ⋮ Efficiently enumerating all maximal cliques with bit-parallelism ⋮ On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem ⋮ Infra-chromatic bound for exact maximum clique search ⋮ A new exact maximum clique algorithm for large and massive sparse graphs ⋮ Finding near-optimal independent sets at scale ⋮ On comparing algorithms for the maximum clique problem ⋮ An exact algorithm for the maximum probabilistic clique problem ⋮ On risk-averse maximum weighted subgraph problems ⋮ Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover ⋮ An improved bit parallel exact maximum clique algorithm ⋮ CliSAT: a new exact algorithm for hard maximum clique problems ⋮ SQBC: an efficient subgraph matching method over large and dense graphs ⋮ Large-scale frequent stem pattern mining in RNA families ⋮ Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications ⋮ Improvements to MCS algorithm for the maximum clique problem ⋮ Incremental Upper Bound for the Maximum Clique Problem ⋮ A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Exact algorithms for maximum clique: a computational study ⋮ Multi-threading a state-of-the-art maximum clique algorithm ⋮ A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs ⋮ Speeding up branch and bound algorithms for solving the maximum clique problem ⋮ A new upper bound for the maximum weight clique problem ⋮ A parallel maximum clique algorithm for large and massive sparse graphs ⋮ A nonconvex quadratic optimization approach to the maximum edge weight clique problem ⋮ A new branch-and-bound algorithm for the maximum weighted clique problem ⋮ Relaxed approximate coloring in exact maximum clique search ⋮ Finding clique clusters with the highest betweenness centrality ⋮ An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs ⋮ Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound ⋮ On the Power of Simple Reductions for the Maximum Independent Set Problem ⋮ A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem ⋮ Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements ⋮ Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection ⋮ A maximum edge-weight clique extraction algorithm based on branch-and-bound ⋮ An enhanced bitstring encoding for exact maximum clique search in sparse graphs ⋮ A parallel branch and bound algorithm for the maximum labelled clique problem
Uses Software
This page was built for publication: A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
