Prize-Collecting Steiner Tree and Forest in Planar Graphs

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

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

     

Profile ID: LFWR-SCP-O-108737

All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.