Linear approximation of shortest superstrings
作者： Avrim Blum , Tao Jiang , Ming Li , John Tromp , Mihalis Yannakakis
关键词:
摘要: … the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4n. Furthermore, we present a simple modified version of the greedy algorithm that …
core.ac.uk
acm.org
sci-hub.se 参考文章(10)
A. Lesk, Computational molecular biology Oxford University Press, Inc.. ,(1988)
Esko Ukkonen, Jorma Tarhio, Hannu Peltola, Hans Söderlund, Algorithms for Some String Matching Problems Arising in Molecular Genetics. ifip congress. pp. 59- 64 ,(1983)
James A. Storer, Data compression: methods and theory Computer Science Press, Inc.. ,(1987)
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
L. G. Valiant, A theory of the learnable symposium on the theory of computing. ,vol. 27, pp. 1134- 1142 ,(1984) , 10.1145/800057.808710
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
Christos Papadimitriou, Mihalis Yannakakis, Optimization, approximation, and complexity classes symposium on the theory of computing. pp. 229- 234 ,(1988) , 10.1145/62212.62233
Kenneth Steiglitz, Christos H. Papadimitriou, Combinatorial Optimization: Algorithms and Complexity ,(1981)
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
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