A simple and faster branch-and-bound algorithm for finding a maximum clique

DOI10.1007/978-3-642-11440-3_18MaRDI QIDQ3404446zbMATH OpenOpenAlexFDO

Authors Etsuji Tomita, Yoichi Sutani, Takanori Higashi, Shinya Takahashi, Mitsuo Wakatsuki

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

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• A fast algorithm for the maximum clique problem
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• scientific article; zbMATH DE number 2040957
• An improved branch and bound algorithm for the maximum clique problem

Cited in

(51)

• A fast algorithm for the maximum weight clique problem
• A fast algorithm for the maximum clique problem
• 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
• On comparing algorithms for the maximum clique problem
• Large-scale frequent stem pattern mining in RNA families
• Exact algorithms for maximum clique: a computational study
• Multi-threading a state-of-the-art maximum clique algorithm
• A new upper bound for the maximum weight clique problem
• A nonconvex quadratic optimization approach to the maximum edge weight clique problem
• An improved bit parallel exact maximum clique algorithm
• A new branch-and-bound algorithm for the maximum weighted clique problem
• 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
• Speeding up branch and bound algorithms for solving the maximum clique problem
• Relaxed approximate coloring in exact maximum clique search
• A parallel branch and bound algorithm for the maximum labelled clique problem
• Improvements to MCS algorithm for the maximum clique problem
• A review on algorithms for maximum clique problems
• Scale reduction techniques for computing maximum induced bicliques
• On the power of simple reductions for the maximum independent set problem
• Speeding up MCS algorithm for the maximum clique problem with ILS heuristic and other enhancements
• An improved branch and bound algorithm for the maximum clique problem
• Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
• A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem
• Infra-chromatic bound for exact maximum clique search
• A new exact maximum clique algorithm for large and massive sparse graphs
• An exact algorithm for the maximum probabilistic clique problem
• On risk-averse maximum weighted subgraph problems
• scientific article; zbMATH DE number 1947416 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• A much faster branch-and-bound algorithm for finding a maximum clique
• Improved infra-chromatic bound for exact maximum clique search
• A local core number based algorithm for the maximum clique problem
• Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
• Incremental Upper Bound for the Maximum Clique Problem
• Why is maximum clique often easy in practice?
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• A parallel maximum clique algorithm for large and massive sparse graphs
• An enhanced bitstring encoding for exact maximum clique search in sparse graphs
• scientific article; zbMATH DE number 2226810 (Why is no real title available?)
• CliSAT: a new exact algorithm for hard maximum clique problems
• Finding the maximum subgraph of prescribed strength
• Finding near-optimal weight independent sets at scale
• Finding clique clusters with the highest betweenness centrality
• A maximum edge-weight clique extraction algorithm based on branch-and-bound
• Finding maximum cliques in arbitrary and in special graphs
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• SQBC: an efficient subgraph matching method over large and dense graphs

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: A simple and faster branch-and-bound algorithm for finding a maximum clique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3404446)