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 (45)

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

This page was built for publication: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments