An algorithm for the steiner problem in graphs
Author:
Abstract
In this paper we consider the Steiner problem in graphs. This is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph. We present two lower bounds for the problem, these bounds being based on two separate Lagrangian relaxations of a zero‐one integer programming formulation of the problem. Problem reduction tests derived from both the original problem and the Lagrangian relaxations are given. Incorporating the bounds and the reduction tests into a tree search procedure enables us to solve problems involving the connection of up to 50 vertices in a graph with 200 undirected arcs and 100 vertices.Keywords
This publication has 11 references indexed in Scilit:
- An algorithm for the steiner problem in graphsNetworks, 1982
- An integer linear programming approach to the steiner problem in graphsNetworks, 1980
- Validation of subgradient optimizationMathematical Programming, 1974
- Cost-minimal trees in directed acyclic graphsMathematical Methods of Operations Research, 1974
- Lagrangean relaxation for integer programming1974
- Steiner's problem in graphs and its implicationsNetworks, 1971
- The steiner problem in graphsNetworks, 1971
- On the Problem of SteinerCanadian Mathematical Bulletin, 1961
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957