On the location of Steiner points in uniformly-oriented Steiner trees

Benny Kjær Nielsen; Pawel Winter; Martin Zachariasen

doi:10.1016/S0020-0190(02)00208-9

On the location of Steiner points in uniformly-oriented Steiner trees

Benny Kjær Nielsen, Pawel Winter, Martin Zachariasen

Náttúruvísindadeildin - Faculty of Science and Technology

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

We give a fundamental result on the location of Steiner points for Steiner minimum trees in uniform orientation metrics. As a corollary we obtain a linear time algorithm for constructing a Steiner minimum tree for a given full topology when the number of uniform orientations is λ=3m,m⩾1.

Original language	English
Pages (from-to)	237-241
Number of pages	5
Journal	Information Processing Letters
Volume	83
Issue number	5
DOIs	https://doi.org/10.1016/S0020-0190(02)00208-9
Publication status	Published - 2002

Keywords

computational geometry
interconnection networks
Steiner trees

Access to Document

10.1016/S0020-0190(02)00208-9

Cite this

@article{30645c7d10394372a5ee51f399c8cab2,

title = "On the location of Steiner points in uniformly-oriented Steiner trees",

abstract = "We give a fundamental result on the location of Steiner points for Steiner minimum trees in uniform orientation metrics. As a corollary we obtain a linear time algorithm for constructing a Steiner minimum tree for a given full topology when the number of uniform orientations is λ=3m,m⩾1.",

keywords = "computational geometry, interconnection networks, Steiner trees",

author = "Nielsen, {Benny Kj{\ae}r} and Pawel Winter and Martin Zachariasen",

year = "2002",

doi = "10.1016/S0020-0190(02)00208-9",

language = "English",

volume = "83",

pages = "237--241",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - On the location of Steiner points in uniformly-oriented Steiner trees

AU - Nielsen, Benny Kjær

AU - Winter, Pawel

AU - Zachariasen, Martin

PY - 2002

Y1 - 2002

N2 - We give a fundamental result on the location of Steiner points for Steiner minimum trees in uniform orientation metrics. As a corollary we obtain a linear time algorithm for constructing a Steiner minimum tree for a given full topology when the number of uniform orientations is λ=3m,m⩾1.

AB - We give a fundamental result on the location of Steiner points for Steiner minimum trees in uniform orientation metrics. As a corollary we obtain a linear time algorithm for constructing a Steiner minimum tree for a given full topology when the number of uniform orientations is λ=3m,m⩾1.

KW - computational geometry

KW - interconnection networks

KW - Steiner trees

U2 - 10.1016/S0020-0190(02)00208-9

DO - 10.1016/S0020-0190(02)00208-9

M3 - Article

SN - 0020-0190

VL - 83

SP - 237

EP - 241

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

On the location of Steiner points in uniformly-oriented Steiner trees

Abstract

Keywords

Access to Document

Fingerprint

Cite this