کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418552 | 681684 | 2011 | 18 صفحه PDF | دانلود رایگان |

The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Set. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an O(1.4969n)O(1.4969n) time and polynomial space algorithm.
► We give the currently fastest exact algorithm for the Dominating Set problem.
► We obtain this algorithm by considering a series of branch-and-reduce algorithms.
► Each algorithm in the series is analysed using the measure and conquer approach.
► This analysis is used to find new rules for the next algorithm in the series.
► The result is an O(1.4969n)O(1.4969n)-time polynomial-space algorithm.
Journal: Discrete Applied Mathematics - Volume 159, Issue 17, 28 October 2011, Pages 2147–2164