Prize-Collecting Steiner Tree and Forest in Planar Graphs

Details Prize-Collecting Steiner Tree and Forest in Planar Graphs Prize-Collecting Steiner Tree and Forest in Planar Graphs

2010-06-22

arxiv.org/abs/1006.4357v1

Computer Science

Data Structures and Algorithms

24 pages

Scientific paper

We obtain polynomial-time approximation-preserving reductions (up to a factor of 1 + \epsilon) from the prize-collecting Steiner tree and prize-collecting Steiner forest problems in planar graphs to the corresponding problems in graphs of bounded treewidth. We also give an exact algorithm for the prize-collecting Steiner tree problem that runs in polynomial time for graphs of bounded treewidth. This, combined with our reductions, yields a PTAS for the prize-collecting Steiner tree problem in planar graphs and generalizes the PTAS of Borradaile, Klein and Mathieu for the Steiner tree problem in planar graphs. Our results build upon the ideas of Borradaile, Klein and Mathieu and the work of Bateni, Hajiaghayi and Marx on a PTAS for the Steiner forest problem in planar graphs. Our main technical result is on the properties of primal-dual algorithms for Steiner tree and forest problems in general graphs when they are run with scaled up penalties.

Affiliated with

Also associated with

No associations

Rating

Prize-Collecting Steiner Tree and Forest in Planar Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Prize-Collecting Steiner Tree and Forest in Planar Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prize-Collecting Steiner Tree and Forest in Planar Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-108737