کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431611 688594 2015 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the hardness of full Steiner tree problems
ترجمه فارسی عنوان
در سختی کامل درختان استینر درخت مشکلات ؟؟
کلمات کلیدی
درخت کامل استینر، بطری کامل استینر را ببندید
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Given a weighted graph G=(V,E)G=(V,E) and a subset R of V, a Steiner tree in G is a tree which spans all vertices in R  . The vertices in V∖RV∖R are called Steiner vertices. A full Steiner tree is a Steiner tree in which each vertex of R is a leaf. The full Steiner tree problem is to find a full Steiner tree with minimum weight. The bottleneck full Steiner tree problem is to find a full Steiner tree which minimizes the length of the longest edge. The k-bottleneck full Steiner tree problem is to find a bottleneck full Steiner tree with at most k Steiner vertices. The smallest full Steiner tree problem is to find a full Steiner tree with the minimum number of Steiner vertices.We show that the full Steiner tree problem in general graphs cannot be approximated within a factor of O(log2−ε⁡|R|)O(log2−ε⁡|R|) for any ε>0ε>0. We also provide a polynomial-time approximation factor preserving reduction from the full Steiner tree problem to the group Steiner tree problem. Based on that, the first approximation algorithm for the full Steiner tree problem in general graphs is obtained. Moreover, we show that the same hardness result holds for the node-weighted version of the full Steiner tree problem. We prove that it is NP-hard to approximate the k  -bottleneck full Steiner tree problem within a factor of 2−ε2−ε. The smallest full Steiner tree problem is shown to be NP-complete and does not admit any polynomial-time O((1−ε)ln⁡n)O((1−ε)ln⁡n)-approximation algorithm. The presented reductions show the connection between the full Steiner tree, the group Steiner tree, and the connected set cover problems. In addition, we present an O(|E|log⁡|V|)O(|E|log⁡|V|) time algorithm for the bottleneck full Steiner tree problem which relaxes the assumption, that G is a complete graph, in Chen et al. [7] algorithm.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 34, September 2015, Pages 118–127
نویسندگان
, , ,