On the full and bottleneck full Steiner tree problems

Abstract

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.