✦ LIBER ✦

The Steiner ratio for the dual normed plane

✍ Scribed by Peng-Jun Wan; Ding-Zhu Du; Ronald L. Graham

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 592 KB
Volume: 171
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00080-5

No coin nor oath required. For personal study only.

✦ Synopsis

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 points in the metric space. Du et al. (1993) conjectured that the Steiner ratio on a normed plane is equal to the Steiner ratio on its dual plane. In this paper we show that this conjecture is true for Ixl ~<5.

📜 SIMILAR VOLUMES

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

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

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

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

A primal-dual approximation algorithm fo

A primal-dual approximation algorithm for the Steiner forest problem

✍ R. Ravi 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 502 KB

An approximation scheme for some Steiner

An approximation scheme for some Steiner tree problems in the plane

✍ Wang, Lusheng; Jiang, Tao 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 536 KB

We design a polynomial-time approximation scheme for the Steiner tree problem in the plane when the given set of regular points is c-local, i.e., in the minimum-cost spanning tree for the given set of regular points, the length of the longest edge is at most c times the length of the shortest edge.