Long Tours and Short Superstrings (Preliminary Version)
作者： S. Rao Kosaraju , Clifford Stein , James K. Park
DOI:
关键词:
摘要:
参考文章(11)
Artur Czumaj, Leszek Gasieniec, Marek Piotrów, Wojciech Rytter, Parallel and Sequential Approximations of Shortest Superstrings scandinavian workshop on algorithm theory. pp. 95- 106 ,(1994) , 10.1007/3-540-58218-5_9
A. M. Frieze, G. Galbiati, F. Maffioli, On the worst‐case performance of some algorithms for the asymmetric traveling salesman problem Networks. ,vol. 12, pp. 23- 39 ,(1982) , 10.1002/NET.3230120103
John Gallant, David Maier, James Astorer, On finding minimal length superstrings Journal of Computer and System Sciences. ,vol. 20, pp. 50- 58 ,(1980) , 10.1016/0022-0000(80)90004-5
Jonathan S. Turner, Approximation algorithms for the shortest common superstring problem Information & Computation. ,vol. 83, pp. 1- 20 ,(1989) , 10.1016/0890-5401(89)90044-8
Sartaj Sahni, Teofilo Gonzalez, P-Complete Approximation Problems Journal of the ACM. ,vol. 23, pp. 555- 565 ,(1976) , 10.1145/321958.321975
Jorma Tarhio, Esko Ukkonen, A greedy approximation algorithm for constructing shortest common superstrings mathematical foundations of computer science. ,vol. 57, pp. 131- 145 ,(1988) , 10.1016/0304-3975(88)90167-3
Shang-Hua Teng, F. Yao, Approximating shortest superstrings ,(1994)
Nicos Christofides, Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem ,(1976)
Christos H. Papadimitriou, Mihalis Yannakakis, The Traveling Salesman Problem with Distances One and Two Mathematics of Operations Research. ,vol. 18, pp. 1- 11 ,(1993) , 10.1287/MOOR.18.1.1
M. L. Fisher, G. L. Nemhauser, L. A. Wolsey, An Analysis of Approximations for Finding a Maximum Weight Hamiltonian Circuit Operations Research. ,vol. 27, pp. 799- 809 ,(1979) , 10.1287/OPRE.27.4.799