Saving Space by Dynamic Algebraization Based on Tree Decomposition: Minimum Dominating Set

Mahdi Belbasi, Martin Fürer

An algorithm is presented that solves the Minimum Dominating Set problem exactly using polynomial space based on dynamic programming for a tree decomposition. A direct application…