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

DOI10.1007/S10898-006-9039-7zbMATH Open1127.90079OpenAlexW2166742555WikidataQ56210441 ScholiaQ56210441MaRDI QIDQ868636FDOQ868636

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

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

zbMATH Keywords

Algorithm Branch-and-bound Computational experiments Maximum clique Approximate 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)

Cites Work

Cited In (60)

Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound
A study of ACO capabilities for solving the maximum clique problem
Extended and discretized formulations for the maximum clique problem
Finding Cliques in Social Networks: A New Distribution-Free Model
An exact algorithm for the maximum probabilistic 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
Title not available (Why is that?)
Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
A branch and bound algorithm for the maximum clique problem
Optimization Bounds from Binary Decision Diagrams
Towards effective exact methods for the maximum balanced biclique problem in bipartite graphs
General cut-generating procedures for the stable set polytope
On the scalability of biocomputing algorithms: the case of the maximum clique problem
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
Title not available (Why is that?)
Why Is Maximum Clique Often Easy in Practice?
Maximum cut-clique problem: ILS heuristics and a data analysis application
A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs
An approximation Lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network
On comparing algorithms for the maximum clique problem
Analysis of reactive search optimisation techniques for the maximum clique problem and applications. (Summary)
Title not available (Why is that?)
Parallel Maximum Clique Algorithms with Applications to Network Analysis
SQBC: an efficient subgraph matching method over large and dense graphs
Discrete optimization with decision diagrams
A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
Strong lift-and-project cutting planes for the stable set problem
An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
Principles and Practice of Constraint Programming – CP 2004
Multi-threading a state-of-the-art maximum clique algorithm
Speeding up branch and bound algorithms for solving the maximum clique problem
Improvements to MCS algorithm for the maximum clique problem
The stable set problem: clique and nodal inequalities revisited
An Extended Comparison of the Best Known Algorithms for Finding the Unweighted Maximum Clique
A new approximate cluster deletion algorithm for diamond-free graphs
A maximum edge-weight clique extraction algorithm based on branch-and-bound
Incremental Upper Bound for the Maximum Clique Problem
Title not available (Why is that?)
Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements
A sequential elimination algorithm for computing bounds on the clique number of a graph
Efficiently enumerating all maximal cliques with bit-parallelism
A review on algorithms for maximum clique problems
A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem
A \textit{branch} \& \textit{price} algorithm for the minimum cost clique cover problem in max-point tolerance graphs
On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
Exact algorithms for maximum clique: a computational study
A simple and faster branch-and-bound algorithm for finding a maximum clique
A nonconvex quadratic optimization approach to the maximum edge weight clique problem
Reformulations and complexity of the clique interdiction problem by graph mapping
Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
Combining Heuristics for Configuration Problems Using Answer Set Programming
A METHOD FOR COMPUTING UPPER BOUNDS ON THE SIZE OF A MAXIMUM CLIQUE
Certified dominance and symmetry breaking for combinatorial optimisation

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)