The bottleneck selected-internal and partial terminal Steiner tree problems

uTaipei > College of Science > Department of Computer Science > Periodical Articles > Item 987654321/16014

Please use this identifier to cite or link to this item: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16014

Title:	The bottleneck selected-internal and partial terminal Steiner tree problems
Authors:	Chen, Yen-Hung;陳彥宏
Contributors:	臺北市立大學資訊科學系
Date:	2016-10
Issue Date:	2017-07-31 13:51:18 (UTC+8)
Abstract:	Given a complete graph G = (V, E) math formula, a positive length function on edges, and two subsets R of V and math formula of R, the selected-internal Steiner tree is defined to be an acyclic subgraph of G spanning all vertices in R such that no vertex in math formula is a leaf of the subgraph. The bottleneck selected-internal Steiner tree problem is to find a selected-internal Steiner tree T for R and math formula in G such that the length of the largest edge in T is minimized. The partial terminal Steiner tree is defined to be an acyclic subgraph of G spanning all vertices in R such that each vertex in math formula is a leaf of the subgraph. The bottleneck partial terminal Steiner tree problem is to find a partial terminal Steiner tree T for R and math formula in G such that the length of the largest edge in T is minimized. In this article, we show that the bottleneck selected-internal Steiner tree problem is NP-complete. We also show that if there is a math formula-approximation algorithm, math formula, for the bottleneck selected-internal Steiner tree problem on metric graphs (i.e., a complete graph and the lengths of edges satisfy the triangle inequality), then P=NP. Then we extend to show that if there is an math formula-approximation algorithm, math formula, for the bottleneck selected-internal Steiner tree problem, then P=NP, where math formula is any computable function of math formula. Moreover, we present an approximation algorithm with performance ratio of 3 for the bottleneck selected-internal Steiner tree problem on metric graphs. Finally, we present an exact algorithm of math formula time for the bottleneck partial terminal Steiner tree problem.
Relation:	Networks，Vol. 68(4)，P.331-339
Appears in Collections:	[Department of Computer Science] Periodical Articles

Files in This Item:

There are no files associated with this item.

Loading...