An approximate algorithm for finding Steiner Forest.

Posted by Tadeusz A. Kadlubowski on Stack Overflow See other posts from Stack Overflow or by Tadeusz A. Kadlubowski
Published on 2010-04-19T16:38:51Z Indexed on 2010/04/19 16:43 UTC
Read the original article Hit count: 427

Hello.

Consider a weighted graph G=(V,E,w). We are given a family of subsets of vertices V_i. Those sets of vertices are not necessarily disjoint.

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 V_1 = V. In this case a Steiner forest is a spanning tree of the whole graph.

Enough theory. 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?

© Stack Overflow or respective owner

Related posts about graph-theory

Related posts about trees