An O(n log n) average time algorithm for computing the shortest network under a given topology
文献类型：期刊论文
| 作者 | Xue, G; Du, DZ |
| 刊名 | ALGORITHMICA
 |
| 出版日期 | 1999-04-01 |
| 卷号 | 23期号:4页码:354-362 |
| 关键词 | analysis of algorithms Steiner minimum trees shortest network under a given topology |
| ISSN号 | 0178-4617 |
| 英文摘要 | In 1992 F. K. Hwang and J. F. Weng published an O(n(2)) time algorithm for computing the shortest network under a given full Steiner topology interconnecting n fixed points in the Euclidean plane, The Hwang-Weng algorithm can be used to improve substantially existing algorithms for the Steiner minimum tree problem because it reduces the number of different Steiner topologies to be considered dramatically. In this paper we present an improved Hwang-Weng algorithm. While the worst-case time complexity of our algorithm is still O (n(2)), its average time complexity over all the full Steiner topologies interconnecting n fixed points is O (n log n). |
| WOS研究方向 | Computer Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000078197000005 |
| 出版者 | SPRINGER VERLAG |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/14168]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Xue, G |
| 作者单位 | 1.Univ Vermont, Dept Comp Sci, Burlington, VT 05405 USA 2.Univ Minnesota, Dept Comp Sci, Minneapolis, MN 55455 USA 3.Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China |
| 推荐引用方式 GB/T 7714 | Xue, G,Du, DZ. An O(n log n) average time algorithm for computing the shortest network under a given topology[J]. ALGORITHMICA,1999,23(4):354-362. |
| APA | Xue, G,&Du, DZ.(1999).An O(n log n) average time algorithm for computing the shortest network under a given topology.ALGORITHMICA,23(4),354-362. |
| MLA | Xue, G,et al."An O(n log n) average time algorithm for computing the shortest network under a given topology".ALGORITHMICA 23.4(1999):354-362. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。