CSpace
The k-Steiner ratio in the rectilinear plane
Borchers, A; Du, DZ; Gao, B; Wan, PJ
1998-10-01
Source PublicationJOURNAL OF ALGORITHMS
ISSN0196-6774
Volume29Issue:1Pages:1-17
AbstractA Steiner minimum tree (SMT) in the rectilinear plane is the shortest length tree interconnecting a set of points, called the regular points, possibly using additional vertices. A k-size Steiner minimum tree (kSMT) is one that can be split into components where all regular points are leaves and all components have at most k leaves. The k-Steiner ratio in the rectilinear plane, Pk, is the infimum of the ratios SMT/kSMT over all finite sets of regular points. The k-Steiner ratio is used to determine the performance ratio of several recent polynomial-time approximations for Steiner minimum trees. Previously it was known that in the rectilinear plane, rho(2) = 2/3, rho(3) = 4/5, and (2k - 2)/(2k - 1.) less than or equal to rho(k)(L,(1)) less than or equal to (2k - 1)/(2k) for k greater than or equal to 4. In 1991, P. Berman and V. Ramaiyer conjectured that in fact rho(k) = (2k-1)/(2k) for k greater than or equal to 4. In this paper we prove their conjecture. (C) 1998 Academic Press.
Language英语
WOS Research AreaComputer Science ; Mathematics ; Science & Technology - Other Topics
WOS SubjectComputer Science, Theory & Methods ; Mathematics, Applied ; Logic
WOS IDWOS:000076061100001
PublisherACADEMIC PRESS INC
Citation statistics
Cited Times:2[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/13437
Collection中国科学院数学与系统科学研究院
Affiliation1.Univ Minnesota, Dept Comp Sci, Minneapolis, MN 55455 USA
2.Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China
3.Lattice Semicond Corp, Milpitas, CA 95125 USA
4.IIT, Dept Appl Math & Comp Sci, Chicago, IL 60616 USA
Recommended Citation
GB/T 7714
Borchers, A,Du, DZ,Gao, B,et al. The k-Steiner ratio in the rectilinear plane[J]. JOURNAL OF ALGORITHMS,1998,29(1):1-17.
APA Borchers, A,Du, DZ,Gao, B,&Wan, PJ.(1998).The k-Steiner ratio in the rectilinear plane.JOURNAL OF ALGORITHMS,29(1),1-17.
MLA Borchers, A,et al."The k-Steiner ratio in the rectilinear plane".JOURNAL OF ALGORITHMS 29.1(1998):1-17.
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
[Borchers, A]'s Articles
[Du, DZ]'s Articles
[Gao, B]'s Articles
Baidu academic
Similar articles in Baidu academic
[Borchers, A]'s Articles
[Du, DZ]'s Articles
[Gao, B]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Borchers, A]'s Articles
[Du, DZ]'s Articles
[Gao, B]'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.