Computational Experience with Stable Set Relaxations

DOI10.1137/S1052623401394092MaRDI QIDQ4441935zbMATH OpenOpenAlexFDO

Authors Gerald Gruber, Franz Rendl

Publication date 19 January 2004

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s1052623401394092

zbMATH Keywords

semidefinite programmingtheta functionstable set problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Semidefinite programming (90C22)

Recommendations

• scientific article; zbMATH DE number 1594513
• Strong lift-and-project cutting planes for the stable set problem
• Connection between semidefinite relaxations of the max-cut and stable set problems
• An SDP-based approach for computing the stability number of a graph
• Some advances on lovász-schrijver N_+() relaxations of the fractional stable set polytope

Cited in

(30)

• Strengthening Chvátal-Gomory cuts for the stable set problem
• Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
• Dealing with inequality constraints in large-scale semidefinite relaxations for graph coloring and maximum clique problems
• Mathematical programming models and exact algorithms
• An application of the Lovász-Schrijver M(K, K) operator to the stable set problem
• A heuristic for the stability number of a graph based on convex quadratic programming and tabu search
• A new approach to the stable set problem based on ellipsoids
• On the Lovász theta function and some variants
• On different versions of the exact subgraph hierarchy for the stable set problem
• Indirect unstructured hex-dominant mesh generation using tetrahedra recombination
• On extracting maximum stable sets in perfect graphs using Lovász's theta function
• Ellipsoidal relaxations of the stable set problem: theory and algorithms
• Exploring the relationship between max-cut and stable set relaxations
• How tight is the corner relaxation? Insights gained from the stable set problem
• A branch and cut solver for the maximum stable set problem
• Strong SDP based bounds on the cutwidth of a graph
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• A new lift-and-project operator
• Computational experience concerning payoff tables and minimum criterion values over the efficient set
• Strong lift-and-project cutting planes for the stable set problem
• Semidefinite programming and constraint programming
• Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem
• The exact subgraph hierarchy and its vertex-transitive variant for the stable set problem for Paley graphs
• The stable set problem: clique and nodal inequalities revisited
• ON GROTSCHEL-LOVASZ-SCHRIJVER'S RELAXATION OF STABLE SET POLYTOPES
• scientific article; zbMATH DE number 2166870 (Why is no real title available?)
• Maximum stable set formulations and heuristics based on continuous optimization
• Exploiting semidefinite relaxations in constraint programming
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Set packing relaxations of some integer programs

This page was built for publication: Computational Experience with Stable Set Relaxations

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