Algorithms for the minimum diameter terminal Steiner tree problem

Given an undirected connected graph (G=(V(G),E(G),d)) with a function (d(cdot )ge 0) on edges and a subset (Ssubseteq V(G)) of terminals, the minimum diameter terminal Steiner tree problem (MDTSTP) asks for a terminal Steiner tree in (G) of a minimum diameter. In the paper, the diameter of a tree refers to the longest of all the distances between two different leaves of the tree. When (G) is a complete graph and (d(cdot )) is a metric function, we demonstrate that an optimal solution of MDTSTP is monopolar or dipolar and give an (O(|S|cdot |V(G)setminus S|^2)) -time exact algorithm. For the nonmetric version of MDTSTP, we present a simple 2-approximation algorithm with a time complexity of (O(|V(G)setminus S|log |S|)) , as well as two exact algorithms with a time complexity of (O(|S|^3|V(G)|^2)) and (O(|S|cdot |V(G)setminus S|^2+|S|^2cdot |V(G)setminus S|)) , respectively.