𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Worst-case ratios of networks in the rectilinear plane

✍ Scribed by Ulrich Brenner; Jens Vygen

Publisher
John Wiley and Sons
Year
2001
Tongue
English
Weight
231 KB
Volume
38
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For point sets in the rectilinear plane, we consider the following five measures of the interconnect length and prove bounds on the worst‐case ratio: minimum Steiner tree, minimum star, clique, minimum spanning tree, and bounding box. In particular, we prove that, for any set of n points, (n βˆ’ 1) times the shortest Steiner tree is less or equal to the clique unless n = 4 and the minimum spanning tree is less or equal to the shortest star unless n ∈ {3, 4, 5}. Β© 2001 John Wiley & Sons, Inc.

πŸ“œ SIMILAR VOLUMES

Thek-Steiner Ratio in the Rectilinear Pl
Thek-Steiner Ratio in the Rectilinear Plane
✍ Al Borchers; Ding-Zhu Du; Biao Gao; Pengjun Wan πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 240 KB

A Steiner minimum tree SMT in the rectilinear plane is the shortest length tree interconnecting a set of points, called the regular points, possibly using Ε½ . additional vertices. A k-size Steiner minimum tree kSMT is one that can be split into components where all regular points are leaves and all