KMS Of Academy of mathematics and systems sciences, CAS
REDUCING THE STEINER PROBLEM IN A NORMED SPACE | |
DU, DZ; HWANG, FK | |
1992-12-01 | |
发表期刊 | SIAM JOURNAL ON COMPUTING |
ISSN | 0097-5397 |
卷号 | 21期号:6页码:1001-1007 |
摘要 | Consider 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. |
关键词 | STEINER TREE MINKOWSKI SPACE NORMED SPACE |
语种 | 英语 |
WOS研究方向 | Computer Science ; Mathematics |
WOS类目 | Computer Science, Theory & Methods ; Mathematics, Applied |
WOS记录号 | WOS:A1992KB48300001 |
出版者 | SIAM PUBLICATIONS |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.amss.ac.cn/handle/2S8OKBNM/28521 |
专题 | 中国科学院数学与系统科学研究院 |
通讯作者 | DU, DZ |
作者单位 | 1.CHINESE ACAD SCI,INST APPL MATH,BEIJING,PEOPLES R CHINA 2.AT&T BELL LABS,MURRAY HILL,NJ 07974 |
推荐引用方式 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. |
条目包含的文件 | 条目无相关文件。 |
个性服务 |
推荐该条目 |
保存到收藏夹 |
查看访问统计 |
导出为Endnote文件 |
谷歌学术 |
谷歌学术中相似的文章 |
[DU, DZ]的文章 |
[HWANG, FK]的文章 |
百度学术 |
百度学术中相似的文章 |
[DU, DZ]的文章 |
[HWANG, FK]的文章 |
必应学术 |
必应学术中相似的文章 |
[DU, DZ]的文章 |
[HWANG, FK]的文章 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论