Premium
A strong lower bound for the Node Weighted Steiner Tree Problem
Author(s) -
Engevall Stefan,
GötheLundgren Maud,
Värbrand Peter
Publication year - 1998
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199801)31:1<11::aid-net2>3.0.co;2-n
Subject(s) - steiner tree problem , combinatorics , vertex (graph theory) , mathematics , generalization , undirected graph , tree (set theory) , graph , upper and lower bounds , heuristic , discrete mathematics , mathematical optimization , mathematical analysis
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