کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871977 | 684128 | 2016 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An exact algorithm for maximum independent set in degree-5 graphs
ترجمه فارسی عنوان
الگوریتم دقیق برای حداکثر مجموعه مستقل در نمودارهای درجه 5
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم دقیق، الگوریتم نمودار، حداکثر مجموعه مستقل، اندازه گیری و تسخیر، تحلیل انباشته شده،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The maximum independent set problem is a basic NP-hard problem and has been extensively studied in exact algorithms. The maximum independent set problems in low-degree graphs are also important and may be bottlenecks of the problem in general graphs. In this paper, we present a 1.1736nnO(1)-time exact algorithm for the maximum independent set problem in an n-vertex graph with degree bounded by 5, improving the previous running time bound of 1.1895nnO(1). In our algorithm, we show that the graph after applying reduction rules always has a good local structure branching on which will effectively reduce the instance. Based on this, we obtain an improved algorithm without introducing a large number of branching rules.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 199, 30 January 2016, Pages 137-155
Journal: Discrete Applied Mathematics - Volume 199, 30 January 2016, Pages 137-155
نویسندگان
Mingyu Xiao, Hiroshi Nagamochi,