{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:12Z","timestamp":1725664692872},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540616801"},{"type":"electronic","value":"9783540706670"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61680-2_56","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:10:58Z","timestamp":1330276258000},"page":"194-207","source":"Crossref","is-referenced-by-count":3,"title":["Greedy algorithms for the shortest common superstring that are asymtotically optimal"],"prefix":"10.1007","author":[{"given":"Alan","family":"Frieze","sequence":"first","affiliation":[]},{"given":"Wojciech","family":"Szpankowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,6]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"K. Alexander, Shortest Common Superstring of Random Strings, Proc. Combinatorial Pattern Matching, Springer-Verlag, LNCS #807, 164\u2013172, 1994","DOI":"10.1007\/3-540-58094-8_15"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"C.Armen and C.Stein, Short Superstrings and the Structure of Overlapping Strings, Journal of Computational Biology, to appear.","DOI":"10.1089\/cmb.1995.2.307"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"C.Armen and C.Stein, A 2-2\/3 Approximation Algorithm for the Shortest Superstring Problem, Proc. Combinatorial Pattern Matching, 1996.","DOI":"10.1007\/3-540-61258-0_8"},{"key":"15_CR4","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0022-5193(88)80246-7","volume":"135","author":"W. Bains","year":"1988","unstructured":"W. Bains and G. Smith, A Novel Method for Nucleic Acid Sequence Determination, J. Theor. Biol., 135, 303\u2013307, 1988.","journal-title":"J. Theor. Biol."},{"key":"15_CR5","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1145\/179812.179818","volume":"41","author":"A. Blum","year":"1994","unstructured":"A. Blum, T. Jiang, M. Li, J. Tromp, M. Yannakakis, Linear Approximation of Shortest Superstring, J. the ACM, 41, 630\u2013647, 1994; also STOC, 328\u2013336, 1991.","journal-title":"J. the ACM"},{"key":"15_CR6","doi-asserted-by":"crossref","DOI":"10.1002\/0471200611","volume-title":"Elements of Information Theory","author":"T.M. Cover","year":"1991","unstructured":"T.M. Cover and J.A. Thomas, Elements of Information Theory, John Wiley&Sons, New York (1991)."},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"A.Czumaj, L.Gasienic, M.Piotrow and W.Rytter, Parallel and Sequential Approximations of Shortest Superstrings, Proceedings of the Fourth Scandinavian Workshop on Algorithm Theory, 95\u2013106, 1994.","DOI":"10.1007\/3-540-58218-5_9"},{"key":"15_CR8","first-page":"59","volume":"1","author":"R. Drmanac","year":"1992","unstructured":"R. Drmanac and C. Crkvenjakov, Sequencing by Hybridization (SBH) with Oligonucloide Probes as an Integral Approach for the Analysis of Complex Genome, Int. J. genomic Research, 1, 59\u201379, 1992.","journal-title":"Int. J. genomic Research"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J. Gallant","year":"1980","unstructured":"J. Gallant, D. Maier and J.A. Storer, On Finding Minimal Length Superstrings, Journal of Computer and System Sciences, 20, 50\u201358, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR10","doi-asserted-by":"crossref","first-page":"1470","DOI":"10.1109\/18.133271","volume":"37","author":"P. Jacquet","year":"1991","unstructured":"P. Jacquet and W. Szpankowski, Analysis of Digital Tries with Markovian Dependency, IEEE Trans. on Information Theory, 37, 1470\u20131475, 1991.","journal-title":"IEEE Trans. on Information Theory"},{"key":"15_CR11","first-page":"385","volume-title":"Approximating Shortest Superstring with Constraints","author":"T. Jiang","year":"1993","unstructured":"T. Jiang and M. Li, Approximating Shortest Superstring with Constraints, WADS, 385\u2013396, Montreal 1993."},{"key":"15_CR12","unstructured":"T.Jiang, Z.Jiang and D.Breslauer, Rotation of Periodic Strings and Short Superstrings, Proceedings of the Third South American Conference on String Processing, to appear."},{"key":"15_CR13","unstructured":"D. E. Knuth, The Art of Computer Programming. Sorting and Searching, Addison-Wesley 1973."},{"key":"15_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/rsa.3240010102","volume":"1","author":"D. E. Knuth","year":"1990","unstructured":"D. E. Knuth, Motwani, and B. Pittel, Stable Husbands, Random Structures and Algorithms, 1, 1\u201314, 1990.","journal-title":"Random Structures and Algorithms"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"S.R.Kosaraju, J.K.Park and C.Stein, Long Tours and Short Superstrings, Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 166\u2013177, 1994.","DOI":"10.1109\/SFCS.1994.365696"},{"key":"15_CR16","unstructured":"A. Lesek (Ed.), Computational Molecular Biology, Sources and Methods for Sequence Analysis, Oxford University Press, 1988."},{"key":"15_CR17","unstructured":"Ming Li, Towards a DNA Sequencing Theory, Proc. of 31st IEEE Symp. on Foundation of Computer Science, 125\u2013134 1990."},{"key":"15_CR18","unstructured":"T. Luczak and W. Szpankowski, A Lossy Data Compression Based on an Approximate Pattern Matching, IEEE Trans. Information Theory, to appear; also Purdue University, CSD-TR-94-072, 1994."},{"key":"15_CR19","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/07391102.1989.10507752","volume":"7","author":"P. Pevzner","year":"1989","unstructured":"P. Pevzner, l-tuple DNA Sequencing: Computer Analysis, J. Biomolecular Structure and Dynamics, 7, 63\u201373, 1989.","journal-title":"J. Biomolecular Structure and Dynamics"},{"key":"15_CR20","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1214\/aop\/1176993000","volume":"18","author":"B. Pittel","year":"1985","unstructured":"B. Pittel, Asymptotic Growth of a Class of Random Trees, Ann. Probab., 18, 414\u2013427, 1985.","journal-title":"Ann. Probab."},{"key":"15_CR21","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1214\/aop\/1176989934","volume":"20","author":"P. Shields","year":"1992","unstructured":"P. Shields, Entropy and Prefixes, Ann. Probab., 20, 403\u2013409, 1992.","journal-title":"Ann. Probab."},{"key":"15_CR22","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0020-0190(88)90137-8","volume":"28","author":"W. Szpankowski","year":"1988","unstructured":"W. Szpankowski, The Evaluation of an Alternative (sic!) Sum with Applications to the Analysis of Some Data Structures, Information Processing Letters, 28, 13\u201319, 1988.","journal-title":"Information Processing Letters"},{"key":"15_CR23","doi-asserted-by":"crossref","first-page":"1176","DOI":"10.1137\/0222070","volume":"22","author":"W. Szpankowski","year":"1993","unstructured":"W. Szpankowski, A Generalized Suffix Tree and its (Un)Expected Asymptotic Behaviors, SIAM J. Computing, 22, pp. 1176\u20131198, 1993.","journal-title":"SIAM J. Computing"},{"key":"15_CR24","unstructured":"S. Teng and F. Yao, Approximating Shortest Superstring, Proc. FOCS, 158\u2013165, 1993."},{"key":"15_CR25","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/BF01840391","volume":"5","author":"E. Ukkonen","year":"1990","unstructured":"E. Ukkonen, A Linear-Time Algorithm for Finding Approximate Shortest Common Superstrings, Algorithmica, 5, 313\u2013323, 1990.","journal-title":"Algorithmica"},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"E. Ukkonen, Approximate String-Matching over Suffix Trees, Proc. Combinatorial Pattern Matching, 228\u2013242, Padova, 1993.","DOI":"10.1007\/BFb0029808"},{"key":"15_CR27","unstructured":"E-H. Yang and Z. Zhang, The Shortest Common Superstring Problem: Average Case Analysis for Both Exact Matching and Approximate Matching, preprint."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61680-2_56.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:09:12Z","timestamp":1605629352000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61680-2_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616801","9783540706670"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-61680-2_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}