Some structural and geometric properties of two-connected Steiner networks

Kenneth Hvam, Line Reinhardt, Pawel Winter, Martin Zachariassen

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review

Abstract

We consider the problem of constructing a shortest
Euclidean 2-connected Steiner network (SMN) for a
set of terminals. This problem has natural applica-
tions in the design of survivable communication net-
works. A SMN decomposes into components that
are full Steiner trees. Winter and Zachariasen proved
that all cycles in SMNs with Steiner points must have
two pairs of consecutive terminals of degree 2. We
use this result and the notion of reduced block-bridge
trees of Luebke to show that no component in a SMN
spans more than approximately one-third of the ter-
minals. Furthermore, we show that no component
spans more than two terminals on the boundary of
the convex hull of the terminals; such two terminals
must in addition be consecutive on the boundary of
this convex hull. Algorithmic implications of these
results are discussed
OriginalsprogEngelsk
TitelCATS 2007 : Proceedings of the Thirteenth Australasian Symposium on Theory of Compting, Ballarat, Victoria, Australia, January 30 - February 02, 2007
RedaktørerJoachim Gudmundsson, Barry Jay
Antal sider7
ForlagAssociation for Computing Machinery
Publikationsdato2007
Sider85-90
ISBN (Trykt)1-920-68246-5
StatusUdgivet - 2007
Udgivet eksterntJa
Begivenhed13th Australasian Symposium on Theory of Computing - Ballarat, Australien
Varighed: 30 jan. 20072 feb. 2007
Konferencens nummer: 13

Symposium

Symposium13th Australasian Symposium on Theory of Computing
Nummer13
Land/OmrådeAustralien
ByBallarat
Periode30/01/200702/02/2007
NavnConferences in Research and Practice in Information Technology
Nummer65
ISSN1445-1336

Citer dette