Name
Abstract | ||
|---|---|---|
The stability number #(G) for a given graph G is the size of a maximum stable set inG. The Lovasz theta number provides an upper bound on #(G) and can be computed inpolynomial time as the optimal value of the Lovasz semidefinite program. In this paper,we show that restricting the matrix variable in the Lovasz semidefinite program to berank-one and rank-two, respectively, yields a pair of continuous, nonlinear optimizationproblems each having the global optimal value #(G). We propose... |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/s10107-002-0356-4 | Math. Program. |
Keywords | Field | DocType |
Computational Result,Polynomial Time,Nonlinear Optimization,Matrix Variable,Continuous Optimization | Continuous optimization,Discrete mathematics,Combinatorics,Mathematical optimization,Upper and lower bounds,Nonlinear programming,Heuristics,Independent set,Vertex cover,Time complexity,Semidefinite programming,Mathematics | Journal |
Volume | Issue | ISSN |
94 | 1 | 0025-5610 |
Citations | PageRank | References |
27 | 2.19 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Burer | 1 | 1148 | 73.09 |
| Renato D. C. Monteiro | 2 | 1250 | 138.18 |
| Yin Zhang | 3 | 687 | 36.24 |