A strong lower bound for the node weighted Steiner tree problem

A strong lower bound for the node weighted Steiner tree problem

0.00 Avg rating0 Votes
Article ID: iaor20022472
Country: United States
Volume: 31
Issue: 1
Start Page Number: 11
End Page Number: 17
Publication Date: Jan 1998
Journal: Networks
Authors: , ,
Keywords: Steiner problem
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.

Reviews

Required fields are marked *. Your email address will not be published.