کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328513 | 684040 | 2005 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of the directed spanning cactus problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper we study the complexity of finding a spanning cactus in various graphs. First, we show that the task of determining if there is a directed spanning cactus in a general unweighted digraph is NP-complete. The proof is a reduction from ONE-IN-THREE 3SAT. Secondly, we show that finding the minimum spanning cactus in a directed, weighted complete graph with triangle inequality is polynomial time equivalent to finding the minimum travelling salesman problem (TSP) tour in the same graph and that they have the same hardness in approximation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 146, Issue 1, 15 February 2005, Pages 81-91
Journal: Discrete Applied Mathematics - Volume 146, Issue 1, 15 February 2005, Pages 81-91
نویسندگان
Anna Palbom,