On finding minimal length superstrings
作者： John Gallant , David Maier , James Astorer
DOI: 10.1016/0022-0000(80)90004-5
关键词:
摘要: Abstract A superstring of a set strings {s1,…, sn} is string s containing each si, 1 ⩽ i n, as substring. The problem is: Given S and positive integer K, does have length K? has applications to data storage; specifically, compression. We consider the complexity problem. NP-completeness results dealing with sets over both finite infinite alphabets are presented. Also, for restricted version problem, linear time algorithm given.
core.ac.uk
elsevier.com
sci-hub.se 参考文章(7)
Aho AV, JE Hopcroft, JD Ullman, The Design and Analysis of Computer Algorithms ,(1974)
M.R. Garey, D.S. Johnson, L. Stockmeyer, Some simplified NP-complete graph problems Theoretical Computer Science. ,vol. 1, pp. 237- 267 ,(1976) , 10.1016/0304-3975(76)90059-1
M. R. Garey, D. S. Johnson, L. Stockmeyer, Some simplified NP-complete problems Proceedings of the sixth annual ACM symposium on Theory of computing - STOC '74. pp. 47- 63 ,(1974) , 10.1145/800119.803884
Stephen A. Cook, The complexity of theorem-proving procedures symposium on the theory of computing. pp. 151- 158 ,(1971) , 10.1145/800157.805047
David Huffman, A Method for the Construction of Minimum-Redundancy Codes Proceedings of the IRE. ,vol. 40, pp. 1098- 1101 ,(1952) , 10.1109/JRPROC.1952.273898
Richard M. Karp, Reducibility Among Combinatorial Problems. Complexity of Computer Computations. pp. 85- 103 ,(1972)
Frank Harary, Graph theory ,(1969)