کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949739 | 1440204 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximate association via dissociation
ترجمه فارسی عنوان
انجمن تقریبی از طریق جدا شدن
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
انجمن مجموعه (پاک کردن خوشه خوشه)، مجموعه تلفیقی نمودار خوشه ای، تجزیه مدولار، گراف آزاد بدون مثلث،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A vertex set X of a graph G is an association set if each component of GâX is a clique, and a dissociation set if each of these cliques has only one or two vertices. We observe some special structures and show that if none of them exists, then the minimum association set problem can be reduced to the minimum weighted dissociation set problem. This yields the first nontrivial approximation algorithm for the association set problem, with approximation ratio 2.5. The reduction is based on a combinatorial study of modular decomposition of graphs free of these special structures. Further, a novel algorithmic use of modular decomposition enables us to implement our algorithm in O(mn+n2) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 219, 11 March 2017, Pages 202-209
Journal: Discrete Applied Mathematics - Volume 219, 11 March 2017, Pages 202-209
نویسندگان
Jie You, Jianxin Wang, Yixin Cao,