Exact computation of Steiner minimal trees in the plane

A Steiner Minimal Tree (SMT) for a given set A = { a 1, …, a n } in the plane is a tree which interconnects these points and whose total length, i.e., the sum of lengths of the branches, is minimum. To achieve the minimum, the tree may contain other points ( Steiner points) besides a 1, …, a n. Comp...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1986-03, Vol.22 (3), p.151-156
Main Authors: Cockayne, E.J., Hewgill, D.E.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Computation
Computer programming
Computer science
control theory
systems
Exact sciences and technology
Heuristic
Information processing
Mathematical analysis
Matrix
Minimization
plane
Steiner Minimal 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:A Steiner Minimal Tree (SMT) for a given set A = { a 1, …, a n } in the plane is a tree which interconnects these points and whose total length, i.e., the sum of lengths of the branches, is minimum. To achieve the minimum, the tree may contain other points ( Steiner points) besides a 1, …, a n. Computer programs for SMTs are exponential and have so far only been able to solve, in a reasonable time, problems with n ⩽ 15. We present improvements to an algorithm of Winter (1981), which enable us to solve all 17-point problems and an estimated 80% of all randomly generated problems with n⩽ 30.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(86)90062-1