The node‐weighted steiner tree problem
Author:
Abstract
The general Node‐Weighted Steiner Tree problem is an extension of the standard Steiner Tree problem by the addition of node‐associated weights. This article analyzes a special case of that problem, where the set of nodes, which must be included in the solution tree, consists of a single node, and all node weights are negative. The special case is shown to be NP‐Complete, its integer programming formulation is presented, and heuristic procedures are proposed. Using Lagrangian relaxation and subgradient optimization, tight lower bounds were derived and utilized by a branch and bound algorithm. The effectiveness of the developed procedures is demonstrated by a set of computational experiments.Keywords
This publication has 16 references indexed in Scilit:
- Lagrangian relaxation for the star‐star concentrator location problem: Approximation algorithm and boundsNetworks, 1985
- An algorithm for the steiner problem in graphsNetworks, 1984
- Topological design of centralized computer networks—formulations and algorithmsNetworks, 1982
- An algorithm for the steiner problem in graphsNetworks, 1982
- An integer linear programming approach to the steiner problem in graphsNetworks, 1980
- Lagrangean Relaxation Applied to Capacitated Facility Location ProblemsA I I E Transactions, 1978
- On Finding and Updating Spanning Trees and Shortest PathsSIAM Journal on Computing, 1975
- Lagrangean relaxation for integer programming1974
- Steiner's problem in graphs and its implicationsNetworks, 1971
- The steiner problem in graphsNetworks, 1971