A strong lower bound for the Node Weighted Steiner Tree Problem

Stefan Engevall, Maud G�the-Lundgren, Peter V�rbrand

Networks · 1998 · 20 citations · 0 references

Concepts

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. © 1998 John Wiley & Sons, Inc. Networks 31: 11–17, 1998