CSpace
A TIGHT LOWER-BOUND FOR THE STEINER RATIO IN MINKOWSKI PLANES
GAO, B; DU, DZ; GRAHAM, RL
1995-07-15
Source PublicationDISCRETE MATHEMATICS
ISSN0012-365X
Volume142Issue:1-3Pages:49-63
AbstractA 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 AreaMathematics
WOS SubjectMathematics
WOS IDWOS:A1995RK77900004
PublisherELSEVIER SCIENCE BV
Citation statistics
Cited Times:3[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/28046
Collection中国科学院数学与系统科学研究院
Affiliation1.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.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[GAO, B]'s Articles
[DU, DZ]'s Articles
[GRAHAM, RL]'s Articles
Baidu academic
Similar articles in Baidu academic
[GAO, B]'s Articles
[DU, DZ]'s Articles
[GRAHAM, RL]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[GAO, B]'s Articles
[DU, DZ]'s Articles
[GRAHAM, RL]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.