An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications

DOI10.1137/090773313zbMath1207.68442OpenAlexW2045561016MaRDI QIDQ3084226

Danny Hermelin, Dror Rawitz, Reuven Bar Yehuda

Publication date: 15 March 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/090773313

zbMATH Keywords

approximation algorithmsgeneralized vertex coverlocal ratio techniqueNemhauser-Trotter theorem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (7)

Linear kernels for separating a graph into components of bounded size ⋮ Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ The generalized vertex cover problem and some variations ⋮ Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover ⋮ Pareto Complexity of Two-Parameter FPT Problems: A Case Study for Partial Vertex Cover

This page was built for publication: An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications