A tutorial on branch and cut algorithms for the maximum stable set problem
From MaRDI portal
Publication:4918254
DOI10.1111/j.1475-3995.2011.00805.xzbMath1270.90092OpenAlexW2051450977MaRDI QIDQ4918254
Steffen Rebennack, Gerhard Reinelt, Panos M. Pardalos
Publication date: 24 April 2013
Published in: International Transactions in Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1111/j.1475-3995.2011.00805.x
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Related Items
A review on algorithms for maximum clique problems, Solving the maximum vertex weight clique problem via binary quadratic programming, Set covering problem with conflict constraints, On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem, A clique covering MIP model for the irregular strip packing problem, An Integer Programming Formulation for the Maximum k-Subset Intersection Problem, Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, Exact Solution Algorithms for the Chordless Cycle Problem, Polyhedral results and stronger Lagrangean bounds for stable spanning trees, Optimization Bounds from Binary Decision Diagrams, Fixed cardinality stable sets, General cut-generating procedures for the stable set polytope, Polylithic modeling and solution approaches using algebraic modeling systems, A branch and cut algorithm for minimum spanning trees under conflict constraints, Indirect unstructured hex-dominant mesh generation using tetrahedra recombination, Fast maximum weight clique extraction algorithm: optimal tables for branch-and-bound, A note on computational approaches for the antibandwidth problem, The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope, Worst-case analysis of clique MIPs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A branch and cut solver for the maximum stable set problem
- The strong perfect graph theorem
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- An exact algorithm for the maximum clique problem
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- Matrices with the Edmonds-Johnson property
- Weakly bipartite graphs and the max-cut problem
- Test case generators and computational results for the maximum clique problem
- Wheel inequalities for stable set polytopes
- Antiweb-wheel inequalities and their separation problems over the stable set polytopes
- A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the separation of maximally violated mod-\(k\) cuts
- A new trust region technique for the maximum weight clique problem
- Exploring the relationship between max-cut and stable set relaxations
- Recognizing Berge graphs
- A Cutting Plane Algorithm for the Linear Ordering Problem
- Resolution Branch and Bound and an Application: The Maximum Weighted Stable Set Problem
- Finding a Maximum Clique in an Arbitrary Graph
- A global optimization approach for solving the maximum clique problem
- Set Partitioning: A survey
- Using cutting planes to solve the symmetric Travelling Salesman problem
- Continuous Characterizations of the Maximum Clique Problem
- Properties of vertex packing and independence system polyhedra
- On the facial structure of set packing polyhedra
- A branch-and-price approach for the maximum weight independent set problem
- A branch and bound algorithm for the maximum clique problem
- A branch-and-cut algorithm for the maximum cardinality stable set problem
