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

DOI10.1007/S10898-006-9039-7MaRDI QIDQ868636zbMATH OpenOpenAlexWikidataFDO

Authors 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-boundComputational experimentsMaximum cliqueApproximate 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)

Recommendations

• scientific article; zbMATH DE number 2040957
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• A branch and bound algorithm for the maximum clique problem
• A branch and bound algorithm for the maximum clique problem
• A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• An improved branch and bound algorithm for the maximum clique problem
• Erratum: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• scientific article; zbMATH DE number 1947416
• Speeding up branch and bound algorithms for solving the maximum clique problem
• scientific article; zbMATH DE number 1560331

Cites work

• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 1947416 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• scientific article; zbMATH DE number 956840 (Why is no real title available?)
• scientific article; zbMATH DE number 956842 (Why is no real title available?)
• A fast algorithm for the maximum clique problem
• Algorithms for maximum independent sets
• An algorithm for finding a maximum clique in a graph
• An exact algorithm for the maximum clique problem
• Erratum: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• Finding a Maximum Clique in an Arbitrary Graph
• Finding a Maximum Independent Set
• Target-oriented branch and bound method for global optimization
• The maximum clique problem

Cited in

(65)

• Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
• Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
• Reformulations and complexity of the clique interdiction problem by graph mapping
• A study of ACO capabilities for solving the maximum clique problem
• Combining Heuristics for Configuration Problems Using Answer Set Programming
• An exact algorithm for the maximum probabilistic clique problem
• Extended and discretized formulations for the maximum clique problem
• An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem
• A New Branch and Bound Algorithm for the Clique Partitioning Problem
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• An improved branch and bound algorithm for the maximum clique problem
• scientific article; zbMATH DE number 1560332 (Why is no real title available?)
• Finding cliques in social networks: a new distribution-free model
• A branch and bound algorithm for the maximum clique problem
• Optimization Bounds from Binary Decision Diagrams
• A local core number based algorithm for the maximum clique problem
• Towards effective exact methods for the maximum balanced biclique problem in bipartite graphs
• Parallel maximum clique algorithms with applications to network analysis
• On the scalability of biocomputing algorithms: the case of the maximum clique problem
• General cut-generating procedures for the stable set polytope
• An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
• Cliques with maximum/minimum edge neighborhood and neighborhood density
• Solving the maximum vertex weight clique problem via binary quadratic programming
• A parallel branch and bound algorithm for the maximum labelled clique problem
• A simple simulated annealing algorithm for the maximum clique problem
• Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• Maximum cut-clique problem: ILS heuristics and a data analysis application
• Finding cliques in social networks: a new distribution-free model
• A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network
• A METHOD FOR COMPUTING UPPER BOUNDS ON THE SIZE OF A MAXIMUM CLIQUE
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
• On comparing algorithms for the maximum clique problem
• Analysis of reactive search optimisation techniques for the maximum clique problem and applications. (Summary)
• SQBC: an efficient subgraph matching method over large and dense graphs
• scientific article; zbMATH DE number 1947416 (Why is no real title available?)
• Speeding up MCS algorithm for the maximum clique problem with ILS heuristic and other enhancements
• Discrete optimization with decision diagrams
• Strong lift-and-project cutting planes for the stable set problem
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
• Multi-threading a state-of-the-art maximum clique algorithm
• An effective branch-and-bound algorithm for the maximum s-bundle problem
• Speeding up branch and bound algorithms for solving the maximum clique problem
• Principles and Practice of Constraint Programming – CP 2004
• Improvements to MCS algorithm for the maximum clique problem
• An experimental analysis of exact algorithms for the maximum clique problem
• A new approximate cluster deletion algorithm for diamond-free graphs
• The stable set problem: clique and nodal inequalities revisited
• A maximum edge-weight clique extraction algorithm based on branch-and-bound
• An Extended Comparison of the Best Known Algorithms for Finding the Unweighted Maximum Clique
• Lexicographic breadth first-search and branch and bound algorithms for the maximum clique problem
• Incremental Upper Bound for the Maximum Clique Problem
• A sequential elimination algorithm for computing bounds on the clique number of a graph
• Why is maximum clique often easy in practice?
• Efficiently enumerating all maximal cliques with bit-parallelism
• A review on algorithms for maximum clique problems
• A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs
• A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
• Certified dominance and symmetry breaking for combinatorial optimisation
• Exact algorithms for maximum clique: a computational study
• A nonconvex quadratic optimization approach to the maximum edge weight clique problem
• A simple and faster branch-and-bound algorithm for finding a maximum clique

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

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