Back to Search
Start Over
AN EXTENSION OF THE NEMHAUSER-TROTTER THEOREM TO GENERALIZED VERTEX COVERWITH APPLICATIONS.
- Source :
-
SIAM Journal on Discrete Mathematics . 2010, Vol. 24 Issue 1, p287-300. 14p. 2 Diagrams. - Publication Year :
- 2010
-
Abstract
- The Nemhauser-Trotter theorem provides an algorithm which is frequently used as a subroutine in approximation algorithms for the classical Vertex Cover problem. In this paper we present an extension of this theorem so it fits a more general variant of Vertex Cover, namely, the Generalized Vertex Cover problem, where edges are allowed not to be covered at a certain predetermined penalty. We show that many applications of the original Nemhauser-Trotter theorem can be applied using our extension to Generalized Vertex Cover. These applications include a (2-2/d)-approximation algorithm for graphs of bounded degree d, a polynomial-time approximation scheme (PTAS) for planar graphs, a (2 - lg lg n/2 lg n)-approximation algorithm for general graphs, and a 2k kernel for the parameterized Generalized Vertex Cover problem. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 24
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 51827612
- Full Text :
- https://doi.org/10.1137/090773313