Article ID Journal Published Year Pages File Type
419276 Discrete Applied Mathematics 2015 8 Pages PDF
Abstract

We show that very simple algorithms based on local search are polynomial-time approximation schemes for Maximum Independent Set, Minimum Vertex Cover  and Minimum Dominating Set, when the input graphs have a fixed forbidden minor.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Simple PTAS’s for families of graphs excluding a minor
Authors
, ,