A Polynomial Time Approximation Scheme for Optimal Product-Requirement Communication Spanning Trees |
| |
| Authors: | Bang Ye Wu Kun-Mao Chao Chuan Yi Tang |
| |
| Institution: | Department of Computer Science and Information Engineering, Shu-Te University, Yen Chau, Kao Shiung, Taiwan, 824, Republic of Chinaf1;Department of Life Science, National Yang-Ming University, Taipei, Taiwan, 112, Republic of China, f2;Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, Republic of China, f3 |
| |
| Abstract: | Given an undirected graph with nonnegative edge lengths and nonnegative vertex weights, the routing requirement of a pair of vertices is assumed to be the product of their weights. The routing cost for a pair of vertices on a given spanning tree is defined as the length of the path between them multiplied by their routing requirement. The optimal product-requirement communication spanning tree is the spanning tree with minimum total routing cost summed over all pairs of vertices. This problem arises in network design and computational biology. For the special case that all vertex weights are identical, it has been shown that the problem is NP-hard and that there is a polynomial time approximation scheme for it. In this paper we show that the generalized problem also admits a polynomial time approximation scheme. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
