On minimum-weight k-edge connected Steiner networks on metric spaces
文献类型：期刊论文
| 作者 | Hsu, DF; Hu, XD ; Lin, GH
|
| 刊名 | GRAPHS AND COMBINATORICS
 |
| 出版日期 | 2000 |
| 卷号 | 16期号:3页码:275-284 |
| ISSN号 | 0911-0119 |
| 英文摘要 | For a given set of points P in a metric space, let w(k)(P) denote the weight of minimum-weight k-edge connected Steiner network on P divided by the weight of minimum-weight k-edge connected spanning network on P, and let r(k) = inf{w(k)(P)\P}. We show in this paper that for any P, w(k)(P) greater than or equal to 1 - 1/k+2, for even k greater than or equal to 2 and w(k)(P) greater than or equal to 1 - 1/k+1, for odd k greater than or equal to 3. In particular, we prove that for any P in the Euclidean plane, w(4)(P) and w(5)(P) are greater than or equal to root3/2, and r(5) less than or equal to 1/8 (7 + 1/32 + root3/2 - root 129/128); For any P in the rectilinear plane r(k) less than or equal to 1 - 1/3k+1, for odd k greater than or equal to 5. In addition, we prove that there exists an O(\P\(3))-time approximation algorithm for constructing a minimum-weight k-edge connected Steiner network which has approximation ratio of 3/2 for even k and (3/2 + 1/2k) for odd k. |
| WOS研究方向 | Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000168577600003 |
| 出版者 | SPRINGER-VERLAG |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/15231]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Hsu, DF |
| 作者单位 | 1.Fordham Univ, Dept Comp & Informat Sci, Bronx, NY 10458 USA 2.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China |
| 推荐引用方式 GB/T 7714 | Hsu, DF,Hu, XD,Lin, GH. On minimum-weight k-edge connected Steiner networks on metric spaces[J]. GRAPHS AND COMBINATORICS,2000,16(3):275-284. |
| APA | Hsu, DF,Hu, XD,&Lin, GH.(2000).On minimum-weight k-edge connected Steiner networks on metric spaces.GRAPHS AND COMBINATORICS,16(3),275-284. |
| MLA | Hsu, DF,et al."On minimum-weight k-edge connected Steiner networks on metric spaces".GRAPHS AND COMBINATORICS 16.3(2000):275-284. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。