کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10328283 683918 2011 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the approximability of the minimum strictly fundamental cycle basis problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the approximability of the minimum strictly fundamental cycle basis problem
چکیده انگلیسی
We consider the problem of finding a strictly fundamental cycle basis of minimum weight in the cycle space associated with an undirected connected graph G, where a nonnegative weight is assigned to each edge of G and the total weight of a basis is defined as the sum of the weights of all the cycles in the basis. Several heuristics have been proposed to tackle this NP-hard problem, which has some interesting applications. In this paper we show that this problem is APX-hard, even when restricted to unweighted graphs, and hence does not admit a polynomial-time approximation scheme, unless P=NP. Using a recent result on the approximability of lower-stretch spanning trees (Elkin et al. (2005) [7]), we obtain that the problem is approximable within O(log2nloglogn) for arbitrary graphs. We obtain tighter approximability bounds for dense graphs. In particular, the problem restricted to complete graphs admits a polynomial-time approximation scheme.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 4, 28 February 2011, Pages 187-200
نویسندگان
, , ,