A faster approximation algorithm for the Steiner problem in graphs

We present a new implementation of the Kou, Markowsky and Berman algorithm for finding a Steiner tree for a connected, undirected distance graph with a specified subset S of the set of vertices V. The total distance of all edges of this Steiner tree is at most 2(1-1/ l) times that of a Steiner minim...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1988-01, Vol.27 (3), p.125-128
Main Author: Mehlhorn, Kurt
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
approximation algorithm
Computer science
control theory
systems
Exact sciences and technology
graph algorithm
Graphs
Information retrieval. Graph
Logic
Steiner tree
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a new implementation of the Kou, Markowsky and Berman algorithm for finding a Steiner tree for a connected, undirected distance graph with a specified subset S of the set of vertices V. The total distance of all edges of this Steiner tree is at most 2(1-1/ l) times that of a Steiner minimal tree, where l is the minimum number of leaves in any Steiner minimal tree for the given graph. The algorithm runs in O(| E|+| V|log| V|) time in the worst case, where E is the set of all edges and V the set of all vertices in the graph.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(88)90066-X