科研之友
微信
新浪微博
Facebook
分享链接
摘要
Given an undirected connected graph with a function on edges and a subset of terminals, the minimum diameter terminal Steiner tree problem (MDTSTP) asks for a terminal Steiner tree in 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 is a complete graph and is a metric function, we demonstrate that an optimal solution of MDTSTP is monopolar or dipolar and give an -time exact algorithm. For the nonmetric version of MDTSTP, we present a simple 2-approximation algorithm with a time complexity of , as well as two exact algorithms with a time complexity of and , respectively.
- 出版日期2014-11
