Finding paths of length k in O*(2^k) time
作者： Ryan Williams
DOI:
关键词:
摘要: We give a randomized algorithm that determines if given graph has simple path of length at least k in O(2^k poly(n,k)) time.
arxiv.org
harvard.edu参考文章(11)
Jan Karel Lenstra, David Shmoys, The Traveling Salesman Problem: A Computational Study ,(2007)
Daniel N. Rockmore, David K. Maslen, Generalized FFTS - A Survey of Some Recent Results Groups and Computation. pp. 183- 237 ,(1996)
Ioannis Koutis, Faster Algebraic Algorithms for Path and Packing Problems international colloquium on automata languages and programming. pp. 575- 586 ,(2008) , 10.1007/978-3-540-70575-8_47
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
Michael Held, Richard M. Karp, A Dynamic Programming Approach to Sequencing Problems Journal of The Society for Industrial and Applied Mathematics. ,vol. 10, pp. 196- 210 ,(1962) , 10.1137/0110015
Songjian Lu, Fenghui Zhang, Jianer Chen, Sing-Hoi Sze, Improved algorithms for path, matching, and packing problems symposium on discrete algorithms. pp. 298- 307 ,(2007) , 10.5555/1283383.1283415
Richard Bellman, Dynamic Programming Treatment of the Travelling Salesman Problem Journal of the ACM. ,vol. 9, pp. 61- 63 ,(1962) , 10.1145/321105.321111
Manuel Blum, Sampath Kannan, Designing programs that check their work Journal of the ACM. ,vol. 42, pp. 269- 291 ,(1995) , 10.1145/200836.200880
Richard M. Karp, Dynamic programming meets the principle of inclusion and exclusion Operations Research Letters. ,vol. 1, pp. 49- 51 ,(1982) , 10.1016/0167-6377(82)90044-X
Jacob Scott, Trey Ideker, Richard M. Karp, Roded Sharan, Efficient algorithms for detecting signaling pathways in protein interaction networks. Journal of Computational Biology. ,vol. 13, pp. 133- 144 ,(2006) , 10.1089/CMB.2006.13.133