pith. sign in

arxiv: 1410.5778 · v2 · pith:IHUUT6GYnew · submitted 2014-10-21 · 💻 cs.DS · cs.DM

Simple PTAS's for families of graphs excluding a minor

Sergio Cabello , David Gajser This is my paper
classification 💻 cs.DS cs.DM
keywords graphsminimumminorsimplealgorithmsapproximationcoverdominating
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On Supports for graphs of bounded genus

    math.CO 2025-03 unverdicted novelty 6.0

    Existence of bounded-genus supports for cross-free intersection hypergraphs from connected subgraphs of bounded-genus host graphs, generalizing prior planar results.