A STRONG LOWER-BOUND FOR THE NODE WEIGHTED STEINER TREE 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 se nse that vertex weights are considered.; Given an undirected graph, th e 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 minimi zed. We present a new formulation of NSP and derive a Lagrangean bound which used together with a heuristic procedure solves the NSP. Comput ational results are reported on a large set of test problems and optim ality is proven for all the generated instances. (C) 1998 John Wiley & Sons, Inc.