Abstract:
We present a simple algorithm for determining the minimum dominating
number of any graph of bounded pathwidth. The algorithm has running time
O(3t+1n) where n is the size of the graph and t is a fixed pathwidth bound.
We also present an implementation in Python of this algorithm extended to
handle graphs of bounded treewidth.