Computing the Stability Number of a Graph Via Linear and Semidefinite Programming

DOI10.1137/05064401XzbMath1176.90611WikidataQ58051170 ScholiaQ58051170MaRDI QIDQ5444282

Juan Carlos Vera, Luis F. Zuluaga, Javier F. Peña

Publication date: 25 February 2008

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

zbMATH Keywords

polynomials; stability number; copositivity; lifting procedures

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C22: Semidefinite programming

90C05: Linear programming

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Uses Software

• SeDuMi