REDUCING THE STEINER PROBLEM IN A NORMED SPACE
文献类型：期刊论文
| 作者 | DU, DZ; HWANG, FK |
| 刊名 | SIAM JOURNAL ON COMPUTING
 |
| 出版日期 | 1992-12-01 |
| 卷号 | 21期号:6页码:1001-1007 |
| 关键词 | STEINER TREE MINKOWSKI SPACE NORMED SPACE |
| ISSN号 | 0097-5397 |
| 英文摘要 | 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. |
| WOS研究方向 | Computer Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:A1992KB48300001 |
| 出版者 | SIAM PUBLICATIONS |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/28520]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。