A Convex Quadratic Characterization of the Lovász Theta Number
From MaRDI portal
Publication:5470766
DOI10.1137/S0895480104429181zbMath1089.05048MaRDI 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
90C20: Quadratic programming
68R10: Graph theory (including graph drawing) in computer science
90C27: Combinatorial optimization
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
Related Items
Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming, A survey on graphs with convex quadratic stability number, New results for recognizing convex-QP adverse graphs, A proximal bundle method for nonsmooth nonconvex functions with inexact information, A characterization of the weighted Lovász number based on convex quadratic programming, 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, A heuristic for the stability number of a graph based on convex quadratic programming and tabu search, Cliques with maximum/minimum edge neighborhood and neighborhood density, Tightening a copositive relaxation for standard quadratic optimization problems, Extended and discretized formulations for the maximum clique problem, A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming, Maximum cut-clique problem: ILS heuristics and a data analysis application, Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms