کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648882 | 1342434 | 2010 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximation algorithms for the minimum rainbow subgraph problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the minimum rainbow subgraph problem (MRS): given a graph GG, whose edges are coloured with pp colours. Find a subgraph F⊆GF⊆G of GG of minimum order and with pp edges such that each colour occurs exactly once. For graphs with maximum degree Δ(G)Δ(G) there is a greedy polynomial-time approximation algorithm for the MRS problem with an approximation ratio of Δ(G)Δ(G). In this paper we present a polynomial-time approximation algorithm with an approximation ratio of 56Δ for Δ≥2Δ≥2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 20, 28 October 2010, Pages 2666–2670
Journal: Discrete Mathematics - Volume 310, Issue 20, 28 October 2010, Pages 2666–2670
نویسندگان
Stephan Matos Camacho, Ingo Schiermeyer, Zsolt Tuza,