𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A strong lower bound for the Node Weighted Steiner Tree Problem

✍ Scribed by Engevall, Stefan; G�the-Lundgren, Maud; V�rbrand, Peter

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
84 KB
Volume
31
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

A tabu search heuristic for the Steiner
A tabu search heuristic for the Steiner Tree Problem
✍ Gendreau, Michel; Larochelle, Jean-Francois; Sans�, Brunilde 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 342 KB 👁 2 views

The Steiner Tree Problem (STP) in graphs is a well-known NP-hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as ATM, since it appears as the inherent mathematical structure behind multicast communications. In this paper, we present a tabu se

The critical-item, upper bounds, and a b
The critical-item, upper bounds, and a branch-and-bound algorithm for the tree knapsack problem
✍ Shaw, Dong X.; Cho, Geon 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB 👁 2 views

The tree knapsack problem (TKP) is a generalized 0-1 knapsack problem where all the items (nodes) are subjected to a partial ordering represented by a rooted tree. If a node is selected to be packed into the knapsack, then all the items on the path from the selected node to the root must also be pac