کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419276 | 683768 | 2015 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Simple PTAS’s for families of graphs excluding a minor
ترجمه فارسی عنوان
پیاده روی ساده برای خانواده های گراف به جز یک جزئی ؟؟
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
طرح تقریبی چندجمله ای، ممنوعیت جزئی جداساز بهینه سازی محلی، حداکثر مجموعه مستقل، پوشش حداقل ریشه، حداقل مجموعه حاکم
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that very simple algorithms based on local search are polynomial-time approximation schemes for Maximum Independent Set, Minimum Vertex Cover and Minimum Dominating Set, when the input graphs have a fixed forbidden minor.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 189, 10 July 2015, Pages 41–48
Journal: Discrete Applied Mathematics - Volume 189, 10 July 2015, Pages 41–48
نویسندگان
Sergio Cabello, David Gajser,