Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set

Authors Johan M. M. van Rooij, Hans L. Bodlaender



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1329.pdf
  • Filesize: 168 kB
  • 12 pages

Document Identifiers

Author Details

Johan M. M. van Rooij
Hans L. Bodlaender

Cite AsGet BibTex

Johan M. M. van Rooij and Hans L. Bodlaender. Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 657-668, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1329

Abstract

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.
Keywords
  • Exact algorithms
  • exponential time algorithms
  • branch and reduce
  • measure and conquer
  • dominating set
  • computer aided algorithm design

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail