A new bound for the Steiner ratio

Authors:
D. Z. Du and F. K. Hwang

Journal:
Trans. Amer. Math. Soc. **278** (1983), 137-148

MSC:
Primary 05C05; Secondary 51M15

MathSciNet review:
697065

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let denote a given set of points in the euclidean plane. A *Steiner minimal tree* for is the shortest network (clearly, it has to be a tree) interconnecting . Junctions of the network which are not in are called *Steiner points* (those in will be called *regular points*). A shortest tree interconnecting without using any Steiner points is called a *minimal tree*. Let and denote the lengths of a Steiner minimal tree and a minimal tree, respectively. Define to be the greatest lower bound for the ratio over all . We prove .

**[1]**F. R. K. Chung and F. K. Hwang,*A lower bound for the Steiner tree problem*, SIAM J. Appl. Math.**34**(1978), no. 1, 27–36. MR**482833**, 10.1137/0134003**[2]**E. N. Gilbert and H. O. Pollak,*Steiner minimal trees*, SIAM J. Appl. Math.**16**(1968), 1–29. MR**0223269****[3]**R. L. Graham and F. K. Hwang,*A remark on Steiner minimal trees*, Bull. Inst. Math. Acad. Sinica**4**(1976), no. 1, 177–182. MR**0437371****[4]**Z. A. Melzak,*On the problem of Steiner*, Canad. Math. Bull.**4**(1961), 143–148. MR**0125466****[5]**H. O. Pollak,*Some remarks on the Steiner problem*, J. Combinatorial Theory Ser. A**24**(1978), no. 3, 278–295. MR**0491279**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
05C05,
51M15

Retrieve articles in all journals with MSC: 05C05, 51M15

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1983-0697065-3

Article copyright:
© Copyright 1983
American Mathematical Society