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

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

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), 27-36. MR**482833 (81h:05052)****[2]**E. N. Gilbert and H. O. Pollak,*Steiner minimal trees*, SIAM J. Appl. Math.**16**(1968), 1-29. MR**0223269 (36:6317)****[3]**R. L. Graham and F. K. Hwang,*Remarks on Steiner minimal trees*. I, Bull. Inst. Math. Acad. Sinica**4**(1976), 177-182. MR**0437371 (55:10302)****[4]**Z. A. Melzak,*On the problem of Steiner*, Canad. Math. Bull.**4**(1961), 143-148. MR**0125466 (23:A2767)****[5]**H. O. Pollak,*Some remarks on the Steiner problem*, J. Combin. Theory Ser. A**24**(1978), 278-295. MR**0491279 (58:10543)**

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