CSpace
REDUCING THE STEINER PROBLEM IN A NORMED SPACE
DU, DZ; HWANG, FK
1992-12-01
Source PublicationSIAM JOURNAL ON COMPUTING
ISSN0097-5397
Volume21Issue:6Pages:1001-1007
AbstractConsider a set P of points in a normed space whose unit sphere is a d-dimensional symmetric polytope with 2d extreme points. This paper proves that there always exists a Steiner minimum tree whose Steiner points are located only at points whose coordinates appear in points of P. This generalizes a recent result of Snyder on d-dimensional rectilinear space, which itself extends Hanan's well-known and much quoted result on the rectilinear plane. Furthermore, the proof in this paper is much simpler than Snyder's proof, even considerably shorter than Hanan's proof. A consequence of this result is that the Steiner problem for P in such a space is reduced to a Steiner problem on graphs and is solvable by any existing Steiner graph algorithms. The paper also conjectures that such a reduction is impossible if he polytope has more than 2d extreme points and provides partial support for the conjecture.
KeywordSTEINER TREE MINKOWSKI SPACE NORMED SPACE
Language英语
WOS Research AreaComputer Science ; Mathematics
WOS SubjectComputer Science, Theory & Methods ; Mathematics, Applied
WOS IDWOS:A1992KB48300001
PublisherSIAM PUBLICATIONS
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/28521
Collection中国科学院数学与系统科学研究院
Corresponding AuthorDU, DZ
Affiliation1.CHINESE ACAD SCI,INST APPL MATH,BEIJING,PEOPLES R CHINA
2.AT&T BELL LABS,MURRAY HILL,NJ 07974
Recommended Citation
GB/T 7714
DU, DZ,HWANG, FK. REDUCING THE STEINER PROBLEM IN A NORMED SPACE[J]. SIAM JOURNAL ON COMPUTING,1992,21(6):1001-1007.
APA DU, DZ,&HWANG, FK.(1992).REDUCING THE STEINER PROBLEM IN A NORMED SPACE.SIAM JOURNAL ON COMPUTING,21(6),1001-1007.
MLA DU, DZ,et al."REDUCING THE STEINER PROBLEM IN A NORMED SPACE".SIAM JOURNAL ON COMPUTING 21.6(1992):1001-1007.
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
[DU, DZ]'s Articles
[HWANG, FK]'s Articles
Baidu academic
Similar articles in Baidu academic
[DU, DZ]'s Articles
[HWANG, FK]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[DU, DZ]'s Articles
[HWANG, FK]'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.