Using Nondeterminism to Design Efficient Deterministic Algorithms
作者： Jianer Chen , Donald K. Friesen , Weijia Jia , Iyad A. Kanj
关键词:
摘要: In this paper, we illustrate how nondeterminism can be used conveniently and effectively in designing efficient deterministic algorithms. particular, our method gives an O((5.7k)k n) parameterized algorithm for the 3-D matching problem, which significantly improves previous by Downey, Fellows, Koblitz. The generalized to yield improved r-D problem any positive integer r. also employed algorithms other optimization problems as well.
springer.com
sci-hub.st 参考文章(8)
Jianer Chen, Iyad A. Kanj, Weijia Jia, Vertex Cover: Further Observations and Further Improvements workshop on graph theoretic concepts in computer science. pp. 313- 324 ,(1999) , 10.1007/3-540-46784-X_30
Michael Randolph Garey, Johnson: computers and intractability: a guide to the theory of np- completeness (freeman ,(1979)
Oren Patashnik, Donald E. Knuth, Ronald L. Graham, Concrete Mathematics: A Foundation for Computer Science ,(1994)
Viggo Kann, Maximum bounded 3-dimensional matching is MAX SNP-complete Information Processing Letters. ,vol. 37, pp. 27- 35 ,(1991) , 10.1016/0020-0190(91)90246-E
John E. Hopcroft, Richard M. Karp, An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs SIAM Journal on Computing. ,vol. 2, pp. 225- 231 ,(1973) , 10.1137/0202019
Iyad A. Kanj, Weijia Jia, Jianer Chen, Donald K. Friesen, Using nondeterminism to design efficient deterministic algorithms Lecture Notes in Computer Science. pp. 120- 131 ,(2001)
Rodney G. Downey, M. R. Fellows, Parameterized Complexity ,(1998)
J. A. Bondy, U. S. R. Murty, Graph Theory with Applications Macmillan Education UK. ,(1976) , 10.1007/978-1-349-03521-2