Networks · 1998 · 20 citations · 0 references
Natural SciencesComputer ScienceMathematicsAlgorithmsOptimizationTheory Of ComputationCombinatorial OptimizationGraph AlgorithmsGraph TheoryBounding FunctionsLower Bound ComputationSteiner Tree ApproximationSteiner Tree ProblemTree Algorithms
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. © 1998 John Wiley & Sons, Inc. Networks 31: 11–17, 1998