Using Nondeterminism to Design Deterministic Algorithms

摘要

In this paper, we illustrate how nondeterminism can be used conveniently and effectively in designing efficient deterministic algorithms. In particular, our method gives an O((5.7 k){sup}k n) parameterized algorithm for the 3-D matching problem, which significantly improves the previous algorithm by Downey, Fellows, and Koblitz. The algorithm can be generalized to yield an improved algorithm for the r-D matching problem for any positive integer r. The method can also be employed in designing deterministic algorithms for other optimization problems as well.