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
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
| Originalsprog | Engelsk |
|---|---|
| Titel | CATS 2007 : Proceedings of the Thirteenth Australasian Symposium on Theory of Compting, Ballarat, Victoria, Australia, January 30 - February 02, 2007 |
| Redaktører | Joachim Gudmundsson, Barry Jay |
| Antal sider | 7 |
| Forlag | Association for Computing Machinery |
| Publikationsdato | 2007 |
| Sider | 85-90 |
| ISBN (Trykt) | 1-920-68246-5 |
| Status | Udgivet - 2007 |
| Udgivet eksternt | Ja |
| Begivenhed | 13th Australasian Symposium on Theory of Computing - Ballarat, Australien Varighed: 30 jan. 2007 → 2 feb. 2007 Konferencens nummer: 13 |
Symposium
| Symposium | 13th Australasian Symposium on Theory of Computing |
|---|---|
| Nummer | 13 |
| Land/Område | Australien |
| By | Ballarat |
| Periode | 30/01/2007 → 02/02/2007 |
| Navn | Conferences in Research and Practice in Information Technology |
|---|---|
| Nummer | 65 |
| ISSN | 1445-1336 |