A TIGHT LOWER-BOUND FOR THE STEINER RATIO IN MINKOWSKI PLANES | |
GAO, B; DU, DZ; GRAHAM, RL | |
刊名 | DISCRETE MATHEMATICS
![]() |
1995-07-15 | |
卷号 | 142期号:1-3页码:49-63 |
ISSN号 | 0012-365X |
英文摘要 | 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). |
WOS研究方向 | Mathematics |
语种 | 英语 |
出版者 | ELSEVIER SCIENCE BV |
WOS记录号 | WOS:A1995RK77900004 |
内容类型 | 期刊论文 |
源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/28045] ![]() |
专题 | 中国科学院数学与系统科学研究院 |
作者单位 | 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 |
推荐引用方式 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. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论