image thumbnail

An Approximation Solution for the Prize-Collecting Steiner Tree Problem

version 1.1.0.0 (3.81 KB) by Fangzhou Chen
A function giving feasible(not optimal) solutions to the Prize-Collecting Steiner Tree Problem

631 Downloads

Updated 21 Jan 2013

View License

Usage:
The Prize-Collecting Steiner Tree problem (PCST) is to find a tree T = (V',E') of a undirected graph G(V,E) that maximizes profit(T) which is defined as the sum of all node-prizes taken into the solution minus the costs of the edges needed to establish the network.
Use T = FindTree(G,vp) to start the computation.
The function PCTSP(G,vp,r) try to find a optimal prize-collecting steiner tree with the root node to be r.
FindTree run PCTSP multiple times using different vertices as roots to find the best prize-collecting steiner tree.

input format:
The input graph for the program is represented by a matrix G and vector vp.
Assume there are n vertices in the graph. The vertices are denoted by 1, 2, 3,...,n. Then G is an n by n matrix. If G(i,j) is NaN or negative number, there is no edge linking vertex i and vertex j. Otherwise, it means the cost of edge(i,j).
The vector vp stores the scores of the vertices. vp(i) is the score of vertex i.
Example:
G = [-1, 1, -1;
1, -1, 0;
-1, 0, -1;]
vp = [2, 1, 1]
means a graph having 2 edges: e(1,2) with cost 1 and e(2,3) with cost 0. The score on vertex 1 is 2, on vertex 2 is 1, and on vertex 3 is 1.

If G =
[-1 1 10 -1 -1 -1 -1 -1 -1 -1;
1 -1 -1 -1 -1 10 -1 -1 -1 -1;
10 -1 -1 10 1 -1 -1 -1 -1 -1;
-1 -1 1 -1 -1 -1 -1 -1 10 -1;
-1 -1 1 -1 -1 1 10 10 1 -1;
-1 10 -1 -1 1 -1 10 -1 -1 -1;
-1 -1 -1 -1 10 10 -1 -1 -1 -1;
-1 -1 -1 -1 10 -1 -1 -1 -1 100;
-1 -1 -1 10 1 -1 -1 -1 -1 100;
-1 -1 -1 -1 -1 -1 -1 100 100 -1;]

vp = [10 1 1 150 200 1 100 1 1 20];

and FindTree(G,vp) will be
The edge(s) in the tree is(are)
Vertex Vertex Cost
3(1) 5(200) 1
5(200) 6(1) 1
5(200) 9(1) 1
3(1) 4(150) 10
5(200) 7(100) 10
total score is 430.
The numbers in the parentheses are the vertex scores.

You may need to implement a parser by yourself to construct such a matrix and vector from your data files.

Bibliography:
Michel X. Goemans and David P. Williamson: A general approximation techique for constrained forest problems. SIAM Journal on Computing, 24:296-317, 1995.
The program is based on the pseudo code on the Page 19.

Cite As

Fangzhou Chen (2021). An Approximation Solution for the Prize-Collecting Steiner Tree Problem (https://www.mathworks.com/matlabcentral/fileexchange/39916-an-approximation-solution-for-the-prize-collecting-steiner-tree-problem), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2012b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!