A Convex Quadratic Characterization of the Lovász Theta Number
From MaRDI portal
Publication:5470766
DOI10.1137/S0895480104429181zbMath1089.05048OpenAlexW2074300280MaRDI QIDQ5470766
Carlos J. Luz, Alexander Schrijver
Publication date: 1 June 2006
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480104429181
Quadratic programming (90C20) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items (15)
Tightening a copositive relaxation for standard quadratic optimization problems ⋮ A heuristic for the stability number of a graph based on convex quadratic programming and tabu search ⋮ Extended and discretized formulations for the maximum clique problem ⋮ Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms ⋮ Improving an upper bound on the size of \(k\)-regular induced subgraphs ⋮ An axiomatic duality framework for the theta body and related convex corners ⋮ Approximating the maximum size of a \(k\)-regular induced subgraph by an upper bound on the co-\(k\)-plex number ⋮ Cliques with maximum/minimum edge neighborhood and neighborhood density ⋮ A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming ⋮ A proximal bundle method for nonsmooth nonconvex functions with inexact information ⋮ A characterization of the weighted Lovász number based on convex quadratic programming ⋮ A survey on graphs with convex quadratic stability number ⋮ New results for recognizing convex-QP adverse graphs ⋮ Maximum cut-clique problem: ILS heuristics and a data analysis application ⋮ Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming
This page was built for publication: A Convex Quadratic Characterization of the Lovász Theta Number
