Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello.

Background

Consider a weighted graph $G=(V,E,w)$. We are given a family of $k$ disjoint subsets of vertices $V_1, \cdots, V_k$.

A Steiner Forest is a forest that for each subset of vertices $V_i$ connects all of the vertices in this subset with a tree.

Example: only one subset of vertices $V_1 = V$. In this case a Steiner forest is a spanning tree of the whole graph.

Question

Finding such a forest with minimal weight is difficult (NP-complete). Do you know any quicker approximate algorithm to find such a forest with non-optimal weight?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

There is a 2-approximation algorithm, see e.g.

A General Approximation Technique For Constrained Forest Problems, Michel Goemans, David P. Williamson, SIAM Journal on Computing 1992.

For special kind of graphs, better bounds can be obtained: for planar graphs there is a PTAS,

Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx, STOC '10.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.