A STRONG LOWER-BOUND FOR THE NODE WEIGHTED STEINER TREE PROBLEM

Citation
S. Engevall et al., A STRONG LOWER-BOUND FOR THE NODE WEIGHTED STEINER TREE PROBLEM, Networks, 31(1), 1998, pp. 11-17
Citations number
17
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture
Journal title
ISSN journal
00283045
Volume
31
Issue
1
Year of publication
1998
Pages
11 - 17
Database
ISI
SICI code
0028-3045(1998)31:1<11:ASLFTN>2.0.ZU;2-5
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 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.