✦ LIBER ✦

Thek-Steiner Ratio in the Rectilinear Plane

✍ Scribed by Al Borchers; Ding-Zhu Du; Biao Gao; Pengjun Wan

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 240 KB
Volume: 29
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1998.0946

No coin nor oath required. For personal study only.

✦ Synopsis

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 components have at most k leaves. The k-Steiner ratio in the rectilinear plane, , is the infimum of k the ratios SMTrkSMT over all finite sets of regular points. The k-Steiner ratio is used to determine the performance ratio of several recent polynomial-time approximations for Steiner minimum trees. Previously it was known that in the rectilinear

In 1991, P. Berman and V. Ramaiyer conjectured that in fact s 2 k y k . Ž . 1 r 2 k for k G 4. In this paper we prove their conjecture.

📜 SIMILAR VOLUMES

A simple proof of the planar rectilinear

A simple proof of the planar rectilinear Steiner ratio

✍ Jeffrey S. Salowe 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 241 KB

Worst-case ratios of networks in the rec

Worst-case ratios of networks in the rectilinear plane

✍ Ulrich Brenner; Jens Vygen 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 231 KB

## 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__ p

The Steiner ratio for the dual normed pl

The Steiner ratio for the dual normed plane

✍ Peng-Jun Wan; Ding-Zhu Du; Ronald L. Graham 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 592 KB

A minimum Steiner tree for a given set X of points is a network interconnecting the points of X having minimal possible total length. The Steiner ratio for a metric space is the largest lower bound for the ratio of lengths between a minimum Steiner tree and a minimum spanning tree on the same set of

A tight lower bound for the Steiner rati

A tight lower bound for the Steiner ratio in Minkowski planes

✍ Biao Gao; Ding-Zhu Du; Ronald L. Graham 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 804 KB

A minimum Steiner tree for a given set X of points is a network interconnecting the points of X having minimum possible total length. The Steiner ratio for a metric space is the largest lower bound for the ratio of lengths between a minimum Steiner tree and a minimum spanning tree on the same set of

The local Steiner problem in normed plan

The local Steiner problem in normed planes

✍ Konrad J. Swanepoel 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB 👁 2 views

Interconnecting networks in the plane: T

Interconnecting networks in the plane: The steiner case

✍ Dan Trietsch 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 752 KB