Code covered by the BSD License

### Highlights from An Approximation Solution for the Prize-Collecting Steiner Tree Problem

• FindTree(G, vp) G is matrix representing a undirected graph (V,E) have none negtive weighted edges, where the G(i,j) is the cost of edge(i,j)
• PCSTr(G, vp, r) G is matrix representing a undirected graph (V,E) have none negtive weighted edges, where the G(i,j) is the cost of edge(i,j)
• View all files

# An Approximation Solution for the Prize-Collecting Steiner Tree Problem

### Fangzhou Chen (view profile)

18 Jan 2013 (Updated )

A function giving feasible(not optimal) solutions to the Prize-Collecting Steiner Tree Problem

FindTree(G, vp)
```%% G is matrix representing a undirected graph (V,E) have none negtive weighted edges, where the G(i,j) is the cost of edge(i,j)
%% Each vertex in V is denoted by the index 1,2,3,... size(V)
%% vp is vertex penalites, a list of int

function T = FindTree(G, vp)
score = -inf;
T = [];
for i = 1:length(vp)
Temp = PCSTr(G, vp, i);
TempScore = Temp.score;
%{
Debug information
str = sprintf('The edge(s) in tree with root %d and total score is %d', i, TempScore);
disp(str);
disp(' Vertex      Vertex       Cost');

for i = 1: length(Temp.E)
str = sprintf('   %d(%d)         %d(%d)         %d', Temp.E(i).id.i, vp(Temp.E(i).id.i), Temp.E(i).id.j, vp(Temp.E(i).id.j), Temp.E(i).cost);
disp(str);
end
%}
%% disp('---------------------------------------------------------');
if TempScore >= score
score = TempScore;
T = Temp;

end
end

disp('The edge(s) in the tree is(are)');
disp('     Vertex           Vertex          Cost');
for i = 1: length(T.E)
str = sprintf('%4d(%6d)      %4d(%6d)       %4d', T.E(i).id.i, vp(T.E(i).id.i), T.E(i).id.j, vp(T.E(i).id.j), T.E(i).cost);
disp(str);
end
str = sprintf('total score is %d', T.score);
disp(str);

```