The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
- 1 May 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 11 (2) , 196-204
- https://doi.org/10.1137/s0895480195287541
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- A counterexample to Borsuk’s conjectureBulletin of the American Mathematical Society, 1993
- Forbidden intersectionsTransactions of the American Mathematical Society, 1987
- Ramsey numbers and an approximation algorithm for the vertex cover problemActa Informatica, 1985
- Approximation Algorithms for the Set Covering and Vertex Cover ProblemsSIAM Journal on Computing, 1982
- A comparison of the Delsarte and Lovász boundsIEEE Transactions on Information Theory, 1979
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979
- Drei Sätze über die n-dimensionale euklidische SphäreFundamenta Mathematicae, 1933