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

4.0

4.0 | 1 rating Rate this file 23 Downloads (last 30 days) File Size: 3.81 KB File ID: #39916

An Approximation Solution for the Prize-Collecting Steiner Tree Problem

by

 

18 Jan 2013 (Updated )

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

| Watch this File

File Information
Description

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.
 

Required Products MATLAB
MATLAB release MATLAB 8.0 (R2012b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (1)
01 Apr 2013 Justin

Apologies to the author, I missed the part that says this solution is not necessarily optimal - as such the file works as described.

Updates
21 Jan 2013

Updates the annotations in the file

Contact us