An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments

DOI10.1007/s10898-006-9039-7zbMath1127.90079OpenAlexW2166742555WikidataQ56210441 ScholiaQ56210441MaRDI QIDQ868636

Etsuji Tomita, Toshikatsu Kameda

Publication date: 6 March 2007

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-006-9039-7

zbMATH Keywords

AlgorithmBranch-and-boundMaximum cliqueComputational experimentsApproximate coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Parallel Maximum Clique Algorithms with Applications to Network Analysis, Combining Heuristics for Configuration Problems Using Answer Set Programming, A review on algorithms for maximum clique problems, Solving the maximum vertex weight clique problem via binary quadratic programming, 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, An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem, An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network, Extended and discretized formulations for the maximum clique problem, Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, On comparing algorithms for the maximum clique problem, An efficient local search algorithm for solving maximum edge weight clique problem in large graphs, The stable set problem: clique and nodal inequalities revisited, Strong lift-and-project cutting planes for the stable set problem, An exact algorithm for the maximum probabilistic clique problem, Finding Cliques in Social Networks: A New Distribution-Free Model, Unnamed Item, Optimization Bounds from Binary Decision Diagrams, SQBC: an efficient subgraph matching method over large and dense graphs, On the scalability of biocomputing algorithms: the case of the maximum clique problem, 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, A simple simulated annealing algorithm for the maximum clique problem, 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, Towards effective exact methods for the maximum balanced biclique problem in bipartite graphs, General cut-generating procedures for the stable set polytope, Speeding up branch and bound algorithms for solving the maximum clique problem, A nonconvex quadratic optimization approach to the maximum edge weight clique problem, Cliques with maximum/minimum edge neighborhood and neighborhood density, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, 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, A new approximate cluster deletion algorithm for diamond-free graphs, Maximum cut-clique problem: ILS heuristics and a data analysis application, Discrete Optimization with Decision Diagrams, 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, A maximum edge-weight clique extraction algorithm based on branch-and-bound, A parallel branch and bound algorithm for the maximum labelled clique problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Erratum: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact algorithm for the maximum clique problem
• An algorithm for finding a maximum clique in a graph
• The maximum clique problem
• Target-oriented branch and bound method for global optimization
• A fast algorithm for the maximum clique problem
• Finding a Maximum Clique in an Arbitrary Graph
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set