標題: | On the full and bottleneck full Steiner tree problems |
作者: | Chen, YH Lu, CL Tang, CY 生物科技學系 Department of Biological Science and Technology |
公開日期: | 2003 |
摘要: | Given a graph G = (V, E) with a length function on edges and a subset R of V, the full Steiner tree is defined to be a Steiner tree in G with all the vertices of R as its leaves. Then the full Steiner tree problem is to find a full Steiner tree in G with minimum length, and the bottleneck full Steiner tree problem is to find a full Steiner tree T in G such that the length of the largest edge in T is minimized. In this paper, we present a new approximation algorithm with performance ratio 2p for the full Steiner tree problem, where p is the best-known performance ratio for the Steiner tree problem. Moreover, we give an exact algorithm of O(E log E) time to solve the bottleneck full Steiner tree problem. |
URI: | http://hdl.handle.net/11536/28223 |
ISBN: | 3-540-40534-8 |
ISSN: | 0302-9743 |
期刊: | COMPUTING AND COMBINATORICS, PROCEEDINGS |
Volume: | 2697 |
起始頁: | 122 |
結束頁: | 129 |
顯示於類別: | 會議論文 |