5 citations · 27 across the 31 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018
Designing Practical PTASes for Minimum Feedback Vertex Set in Planar Graphs
Glencora Borradaile, Hung Le, Baigong Zheng
We present two algorithms for the minimum feedback vertex set problem in planar graphs: an PTAS using a linear kernel and balanced separator, and a heuristic algorith…
cs.DS2018★ 1 cited
Local Search is a PTAS for Feedback Vertex Set in Minor-free Graphs
Hung Le, Baigong Zheng
We show that a simple local search gives a PTAS for the Feedback Vertex Set (FVS) problem in minor-free graphs. An efficient PTAS in minor-free graphs was known for this problem by…
cs.DS2018
A PTAS for subset TSP in minor-free graphs
Hung Le
We give the first PTAS for the subset Traveling Salesperson Problem (TSP) in -minor-free graphs. This resolves a long standing open problem in a long line of work on designing P…