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