کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950666 | 1364297 | 2017 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Exact algorithms for maximum independent set
ترجمه فارسی عنوان
الگوریتم های دقیق برای مجموعه حداکثر مستقل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم دقیق، مجموعه مستقل، نمودار، چندجمله ای فضا، شعبه و کاهش، اندازه گیری و تسخیر، تحلیل انباشته شده،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We show that the maximum independent set problem on an n-vertex graph can be solved in 1.1996nnO(1) time and polynomial space, which even is faster than Robson's 1.2109nnO(1)-time exponential-space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7, which run in time of 1.1893nnO(1) and 1.1970nnO(1), respectively. Our algorithms are obtained by using fast algorithms for MIS in low-degree graphs in a hierarchical way and making a careful analysis on the structure of bounded-degree graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 255, Part 1, August 2017, Pages 126-146
Journal: Information and Computation - Volume 255, Part 1, August 2017, Pages 126-146
نویسندگان
Mingyu Xiao, Hiroshi Nagamochi,