کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950666 1364297 2017 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Exact algorithms for maximum independent set
ترجمه فارسی عنوان
الگوریتم های دقیق برای مجموعه حداکثر مستقل
کلمات کلیدی
الگوریتم دقیق، مجموعه مستقل، نمودار، چندجمله ای فضا، شعبه و کاهش، اندازه گیری و تسخیر، تحلیل انباشته شده،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, ,