Article ID: | iaor20022472 |
Country: | United States |
Volume: | 31 |
Issue: | 1 |
Start Page Number: | 11 |
End Page Number: | 17 |
Publication Date: | Jan 1998 |
Journal: | Networks |
Authors: | Vrbrand Peter, Engevall Stefan, Gthe-Lundgran Maud |
Keywords: | Steiner problem |
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.