Using nondeterminism to design efficient deterministic algorithms Conference Paper

abstract

• Springer-Verlag Berlin Heidelberg 2001. 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.7k)kn) 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.

name of conference

• FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 21st Conference, Bangalore, India, December 13-15, 2001, Proceedings

authors

• Chen, Jianer

published proceedings

• Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

• Chen, J., Friesen, D. K., Jia, W., & Kanj, I. A.

complete list of authors

• Chen, J||Friesen, DK||Jia, W||Kanj, IA

publication date

• January 2001

published in

• Lecture Notes in Computer Science  Journal

International Standard Book Number (ISBN) 10

• 3540430024

start page

• 120

end page

• 131

volume

• 2245