Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications
verfasst von : Reuven Bar-Yehuda, Danny Hermelin, Dror Rawitz
Erschienen in: Approximation and Online Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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-\frac{2}{d})$
-approximation algorithm for graphs of bounded degree
d
, a PTAS for planar graphs, a
$(2-\frac{\lg \lg n}{2 \lg n})$
-approximation algorithm for general graphs, and a 2
k
kernel for the parameterized
Generalized Vertex Cover
problem.