کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434022 | 689670 | 2014 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A refined exact algorithm for Edge Dominating Set
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this paper, we present a new exact algorithm for the Edge Dominating Set problem, and analyze its running time by the Measure and Conquer method. Our algorithm runs in 1.3160nnO(1)1.3160nnO(1) time for a graph with n vertices, which is the currently fastest known time for the Edge Dominating Set problem. By designing new branching rules based upon conceptually simple local structures, which we call clique-producing vertices and cycles, we obtain an algorithm that is simpler than the previously fastest known algorithm and has an improved time bound as well.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 560, Part 2, 4 December 2014, Pages 207–216
Journal: Theoretical Computer Science - Volume 560, Part 2, 4 December 2014, Pages 207–216
نویسندگان
Mingyu Xiao, Hiroshi Nagamochi,