کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421033 | 684020 | 2006 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minmax subtree cover problem on cacti
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Minmax subtree cover problem on cacti Minmax subtree cover problem on cacti](/preview/png/421033.png)
چکیده انگلیسی
Let G=(V,E)G=(V,E) be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p be a positive integer. The minmax subtree cover problem (MSC) asks to find a pair (X,T)(X,T) of a partition X={X1,X2,…,Xp}X={X1,X2,…,Xp} of V and a set TT of p subtrees T1,T2,…,TpT1,T2,…,Tp, each TiTi containing XiXi so as to minimize the maximum cost of the subtrees, where the cost of TiTi is defined to be the sum of the weights of edges in TiTi and the weights of vertices in XiXi. In this paper, we propose an O(p2n)O(p2n) time (4-4/(p+1))(4-4/(p+1))-approximation algorithm for the MSC when G is a cactus.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 8, 15 May 2006, Pages 1254–1263
Journal: Discrete Applied Mathematics - Volume 154, Issue 8, 15 May 2006, Pages 1254–1263
نویسندگان
Hiroshi Nagamochi, Taizo Kawada,