Name
Abstract | ||
|---|---|---|
In this paper, we study the Node Weighted Steiner Tree Problem (NSP). This problem is a generalization of the Steiner tree problem in the sense that vertex weights are considered.; Given an undirected graph, the problem is to find a tree that spans a subset of the vertices and is such that the total edge cost minus the total vertex weight is minimized. We present a new formulation of NSP and derive a Lagrangean bound which used together with a heuristic procedure solves the NSP. Computational results are reported on a large set of test problems and optimality is proven for all the generated instances. (C) 1998 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1002/(SICI)1097-0037(199801)31:1<11::AID-NET2>3.0.CO;2-N | NETWORKS |
Keywords | Field | DocType |
node weighted Steiner tree problem,prize-collecting Steiner tree problem,Lagrangean relaxation,subgradient optimization | Graph theory,Graph,Mathematical optimization,Combinatorics,Vertex (geometry),Steiner tree problem,Upper and lower bounds,K-ary tree,Spanning tree,Mathematics,Heuristic procedure | Journal |
Volume | Issue | ISSN |
31 | 1 | 0028-3045 |
Citations | PageRank | References |
12 | 1.03 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefan Engevall | 1 | 50 | 4.19 |
| Maud Göthe-Lundgren | 2 | 12 | 1.03 |
| Peter Värbrand | 3 | 247 | 22.37 |