Canonical Forms and Algorithms for Steiner Trees in Uniform Orientation Metrics: DIKU-rapport 02/22

M. Brazil, D. A. Thomas, J. F. Weng, Martin Tvede Zachariasen

Research output: Book/ReportBookpeer-review

Abstract

We present some fundamental structural properties for minimum length
networks (known as Steiner minimum trees) interconnecting a given set of
points in an environment in which edge segments are restricted to uniformly oriented directions. We show that the edge segments of any full
component of such a tree contain a total of at most 4 directions if is not a
multiple of , or 6 directions if is a multiple of . This result allows us to
develop useful canonical forms for these full components.
The structural properties of these Steiner minimum trees are then used to
resolve an important open problem in the area: does there exist a polynomialtime algorithm for constructing a Steiner minimum tree, if the topology of
the tree is known? We obtain a simple linear time algorithm for constructing a Steiner minimum tree for any given set of points and a given Steiner
topology.
Original languageEnglish
Place of PublicationKøbenhavn
PublisherKøbenhavns Universitet - Datalogisk Institut
Number of pages26
Publication statusPublished - 2002

Publication series

NameDIKU-rapport
No.22
Volume02

Keywords

  • steiner tree
  • steiner minimum tree
  • Algorithms

Fingerprint

Dive into the research topics of 'Canonical Forms and Algorithms for Steiner Trees in Uniform Orientation Metrics: DIKU-rapport 02/22'. Together they form a unique fingerprint.

Cite this