KMS Of Academy of mathematics and systems sciences, CAS
A TIGHT LOWER-BOUND FOR THE STEINER RATIO IN MINKOWSKI PLANES | |
GAO, B; DU, DZ; GRAHAM, RL | |
1995-07-15 | |
Source Publication | DISCRETE MATHEMATICS |
ISSN | 0012-365X |
Volume | 142Issue:1-3Pages:49-63 |
Abstract | 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 points in the metric space. In this note, we show that for any Minkowski plane, the Steiner ratio is at least 2/3. This settles a conjecture of Cieslik (1990) and also Du et al. (1991). |
Language | 英语 |
WOS Research Area | Mathematics |
WOS Subject | Mathematics |
WOS ID | WOS:A1995RK77900004 |
Publisher | ELSEVIER SCIENCE BV |
Citation statistics | |
Document Type | 期刊论文 |
Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/28046 |
Collection | 中国科学院数学与系统科学研究院 |
Affiliation | 1.UNIV MINNESOTA,DEPT COMP SCI,MINNEAPOLIS,MN 55455 2.CHINESE ACAD SCI,INST APPL MATH,BEIJING,PEOPLES R CHINA 3.AT&T BELL LABS,MURRAY HILL,NJ 07974 |
Recommended Citation GB/T 7714 | GAO, B,DU, DZ,GRAHAM, RL. A TIGHT LOWER-BOUND FOR THE STEINER RATIO IN MINKOWSKI PLANES[J]. DISCRETE MATHEMATICS,1995,142(1-3):49-63. |
APA | GAO, B,DU, DZ,&GRAHAM, RL.(1995).A TIGHT LOWER-BOUND FOR THE STEINER RATIO IN MINKOWSKI PLANES.DISCRETE MATHEMATICS,142(1-3),49-63. |
MLA | GAO, B,et al."A TIGHT LOWER-BOUND FOR THE STEINER RATIO IN MINKOWSKI PLANES".DISCRETE MATHEMATICS 142.1-3(1995):49-63. |
Files in This Item: | ||||||
There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment