CSpace
ON STEINER MINIMAL-TREES WITH LP DISTANCE
LIU, ZC; DU, DZ
1992
Source PublicationALGORITHMICA
ISSN0178-4617
Volume7Issue:2-3Pages:179-191
AbstractLet L(p) be the plane with the distance d(rho)(A1, A2) = ([x1 - X2[p + [y1 - y2[p)/1p where x(i) and y(i) are the cartesian coordinates of the point A(i). Let P be a finite set of points in L(p). We consider Steiner minimal trees on P. It is proved that, for 1 < p < infinity, each Steiner point is of degree exactly three. Define the Steiner ratio rho(p) to be inf{L(s)(P)/L(m)(P)[P subset-of L(p)} where L(s)(P) and L(m)(P) are lengths of the Steiner minimal tree and the minimal spanning tree on P, respectively. Hwang showed rho-1 = 2/3. Chung and Graham proved rho-2 > 0.842. We prove in this paper that rho(infinity) = 2/3 and square-root(square-root 2/2)rho-1-rho-2 less-than-or-equal-to rho(p) less-than-or-equal-to square-root 3/2 for any p.
KeywordSTEINER TREES SPANNING TREES STEINER RATIO LP DISTANCE BOUNDS
Language英语
WOS Research AreaComputer Science ; Mathematics
WOS SubjectComputer Science, Software Engineering ; Mathematics, Applied
WOS IDWOS:A1992HA31400004
PublisherSPRINGER VERLAG
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/27314
Collection中国科学院数学与系统科学研究院
Corresponding AuthorLIU, ZC
AffiliationCHINESE ACAD SCI,INST APPL MATH,BEIJING,PEOPLES R CHINA
Recommended Citation
GB/T 7714
LIU, ZC,DU, DZ. ON STEINER MINIMAL-TREES WITH LP DISTANCE[J]. ALGORITHMICA,1992,7(2-3):179-191.
APA LIU, ZC,&DU, DZ.(1992).ON STEINER MINIMAL-TREES WITH LP DISTANCE.ALGORITHMICA,7(2-3),179-191.
MLA LIU, ZC,et al."ON STEINER MINIMAL-TREES WITH LP DISTANCE".ALGORITHMICA 7.2-3(1992):179-191.
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
[LIU, ZC]'s Articles
[DU, DZ]'s Articles
Baidu academic
Similar articles in Baidu academic
[LIU, ZC]'s Articles
[DU, DZ]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[LIU, ZC]'s Articles
[DU, DZ]'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.