2026-08-18T06:25:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1329 2024-03-06T10:33:03Z ddc:004 open_access

Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set van Rooij, Johan M. M. Bodlaender, Hans L. Exact algorithms exponential time algorithms branch and reduce measure and conquer dominating set computer aided algorithm design 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. In this paper, we propose to use measure and conquer also as a tool in the design of algorithms. In an iterative process, we can obtain a series of branch and reduce algorithms. A mathematical analysis of an algorithm in the series with measure and conquer results in a quasiconvex programming problem. The solution by computer to this problem not only gives a bound on the running time, but also can give a new reduction rule, thus giving a new, possibly faster algorithm. This makes design by measure and conquer a form of computer aided algorithm design. When we apply the methodology to a Set Cover modelling of the Dominating Set problem, we obtain the currently fastest known exact algorithms for Dominating Set: an algorithm that uses $O(1.5134^n)$ time and polynomial space, and an algorithm that uses $O(1.5063^n)$ time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Johan M. M. van Rooij and Hans L. Bodlaender 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1329 urn:nbn:de:0030-drops-13297 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1329 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode