標題: 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
顯示於類別:會議論文