A Search for the Dominating-Set-Width

Abstract

In this master's thesis we provide a new width measurement definition on graphs. This width measurement determines the number of different dominating sets on a subgraph of a graph. Therefore we call it the dominating-set-width. With this width we create a fixed-parameter tractable dynamic programming algorithm that solves the minimum dominating set problem. Dominating-set-width is based on another width measurement, called boolean-width, which was introduced by Bui-Xuan et al. along with an algorithm that solves the minimum dominating set problem. We will show that our algorithm has a faster run time than the one introduced by Bui-Xuan et al. Furthermore, this master's thesis provides a data structure for this new width, as well as an upper and lower-bound for the width when a graph is restricted to a graph class.