Premium
Efficient path and vertex exchange in steiner tree algorithms
Author(s) -
Duin Cees,
Voβ Stefan
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199703)29:2<89::aid-net3>3.0.co;2-7
Subject(s) - steiner tree problem , vertex (graph theory) , algorithm , computer science , path (computing) , tree (set theory) , combinatorics , mathematics , graph , programming language
Abstract Steiner's problem in a weighted graph requires a tree of minimum total weight spanning a subset of special vertices. In this paper, we formulate efficient routines for greedy exchanges of paths as well as vertices. The heuristic proposed on the basis of these routines consists of three phases: an initialization providing shortest‐path information, a module for the selection of Steiner vertices, and an improvement procedure. The latter procedure constitutes a general procedure executable after any heuristic. A spin‐off from the second module is a decreased running time for a well‐known 11/6 approximation algorithm. The first phase can be replaced by a shortest‐path approximation method to obtain a running time order that is quadratic in the number of vertices. © 1997 John Wiley & Sons, Inc. Inc. Networks, 29: 89–105, 1997