An SDP-based approach for computing the stability number of a graph

DOI10.1007/s00186-022-00773-1zbMath1490.90244arXiv2108.05716OpenAlexW3191501345MaRDI QIDQ2123126

Elisabeth Gaar, Melanie Siebenhofer, Angelika Wiegele

Publication date: 8 April 2022

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2108.05716

zbMATH Keywords

semidefinite programmingcombinatorial optimizationbranch and boundstable setLovász theta function

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items

Strong SDP based bounds on the cutwidth of a graph

Uses Software

• Max-AO
• GitHub

Cites Work

• Unnamed Item
• Unnamed Item
• A boundary point method to solve semidefinite programs
• Geometric algorithms and combinatorial optimization
• Maximum stable set formulations and heuristics based on continuous optimization
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
• Improving ADMMs for solving doubly nonnegative programs through dual factorization
• A bundle approach for SDPs with exact subgraph constraints
• Using a factored dual in augmented Lagrangian methods for semidefinite programming
• A review on algorithms for maximum clique problems
• The stable set problem: clique and nodal inequalities revisited
• Integer Programming
• A Spectral Bundle Method for Semidefinite Programming
• Reducibility among Combinatorial Problems
• Regularization Methods for Semidefinite Programming
• A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems