کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949463 1440190 2017 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Spanning cactus: Complexity and extensions
ترجمه فارسی عنوان
پوشش کاکتوس: پیچیدگی و گسترش
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Minimum spanning cactus and minimum spanning cactus extension problems are studied. Both problems are NP-Complete. We present an approximation algorithm for the minimum spanning cactus extension of a forest, a hardness of approximation result of the general minimum spanning cactus problem. For the minimum spanning cactus extension problem, Kabadi and Punnen presented polynomial time algorithms for extending quasi-stars, spanning trees (Kabadi and Punnen, 2013). We present improved analysis of their algorithms in both cases. We further show that their algorithm for the extension of spanning trees can be generalized to extend any connected spanning partial cactus. As a requirement of improved implementation, we have presented a new O(n3) algorithm to compute all minimum cost monotone paths with respect to a spanning tree.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 233, 31 December 2017, Pages 19-28
نویسندگان
, ,