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

Benny Kjær Nielsen; Pawel Winter; Martin Zachariasen

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

Benny Kjær Nielsen, Pawel Winter, Martin Zachariasen

University of Copenhagen

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

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
Journal	Information Processing Letters
Pages (from-to)	237-241
ISSN	0020-0190
Publication status	Published - 2002
Externally published	Yes

Keywords

Computational geometry
Interconnection networks
Steiner trees

Cite this

@article{1bb2e8908e364e09bff12fbb96227242,

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, Computational geometry, Interconnection networks, Steiner trees",

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

year = "2002",

language = "English",

pages = "237--241",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

}

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

KW - Computational geometry

KW - Interconnection networks

KW - Steiner trees

M3 - Journal article

SN - 0020-0190

SP - 237

EP - 241

JO - Information Processing Letters

JF - Information Processing Letters

ER -

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

Abstract

Keywords

Fingerprint

Cite this