Simple PTAS's for families of graphs excluding a minor

DOI10.1016/j.dam.2015.03.004zbMath1316.05093arXiv1410.5778OpenAlexW2083352539MaRDI QIDQ2352263

Sergio Cabello, David Gajser

Publication date: 30 June 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.5778

zbMATH Keywords

forbidden minorlocal optimizationmaximum independent setpolynomial-time approximation schemeseparatorminimum vertex coverminimum dominating set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Graph minors (05C83) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ Unnamed Item ⋮ Constructing planar support for non-piercing regions ⋮ A Local-Search Algorithm for Steiner Forest ⋮ Limits of local search: quality and efficiency ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A tight analysis of geometric local search

Cites Work

• Unnamed Item
• Approximation algorithms for maximum independent set of pseudo-disks
• Improved results on geometric hitting set problems
• Single source shortest paths in \(H\)-minor free graphs
• Graph minors. XVI: Excluding a non-planar graph
• Independent set of intersection graphs of convex objects in 2D
• Local tree-width, excluded minors, and approximation algorithms
• Guarding terrains via local search
• Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Approximation algorithms for NP-complete problems on planar graphs
• A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–

This page was built for publication: Simple PTAS's for families of graphs excluding a minor