{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:35Z","timestamp":1725664235816},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540600848"},{"type":"electronic","value":"9783540494256"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60084-1_66","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:39:51Z","timestamp":1330277991000},"page":"99-110","source":"Crossref","is-referenced-by-count":0,"title":["NC algorithms for finding a maximal set of paths with application to compressing strings"],"prefix":"10.1007","author":[{"given":"Zhi-Zhong","family":"Chen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"9_CR1","unstructured":"C. Armen and C. Stein, A 2 3\/4-Approximation Algorithm for the Shortest Superstring Problem, unpublished manuscript, 1994."},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"A. Blum, T. Jiang, M. Li, J. Tromp, and M. Yannakakis, Linear Approximation of Shortest Superstrings, in: Proc. 23rd ACM Symp. on Theory of Computing (ACM, 1991) 328\u2013336.","DOI":"10.1145\/103418.103455"},{"key":"9_CR3","first-page":"95","volume-title":"Lecture Notes in Computer Science, Vol. 824","author":"A. Czumaj","year":"1994","unstructured":"A. Czumaj, L. Gasieniec, M. Piotrow, and W. Rytter, Parallel and Sequential Approximation of Shortest Superstrings, in: Proc. 4th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 824 (Springer, Berlin, 1994) 95\u2013106."},{"key":"9_CR4","doi-asserted-by":"crossref","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. Storer, On Finding Minimal Length Superstrings, Journal of Computer and System Sciences\n20 (1980) 50\u201358.","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"N. Karmarkar and R.M. Karp, An Efficient Approximation Scheme for the One-Dimensional Bin Packing Problem, in: Proc. 23rd IEEE Symp. on Foundations of Computer Science (IEEE, 1982) 312\u2013320.","DOI":"10.1109\/SFCS.1982.61"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"M. Li, Towards a DNA Sequencing Theory (Learning a String), in: Proc. 31st IEEE Symp. on Foundations of Computer Science (IEEE, 1990) 125\u2013134.","DOI":"10.1109\/FSCS.1990.89531"},{"key":"9_CR7","unstructured":"H. Peltola, H. Soderlund, J. Tarhio, and E. Ukkonen, Algorithms for Some String Matching Problems Arising in Molecular Genetics, in: Proc. 2nd IFIP Congress (1983) 53\u201364."},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"S. Rao Kosaraju, J.K. Park, and C. Stein, Long Tours and Short Superstrings, in: Proc. 35th IEEE Symp. on Foundations of Computer Science (IEEE, 1994) 166\u2013177.","DOI":"10.1109\/SFCS.1994.365696"},{"key":"9_CR9","unstructured":"J. Storer, Data Compression: Methods and Theory (Computer Science Press, 1988)."},{"key":"9_CR10","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","volume":"57","author":"J. Tarhio","year":"1988","unstructured":"J. Tarhio and E. Ukkonen, A Greedy Approximation Algorithm for Constructing Shortest Common Superstrings, Theoretical Computer Science\n57 (1988) 131\u2013145.","journal-title":"Theoretical Computer Science"},{"key":"9_CR11","unstructured":"S.-H. Teng and F. Yao, Approximating Shortest Superstrings, in: Proc. 34th IEEE Symp. on Foundations of Computer Science (IEEE, 1993) 158\u2013165."},{"key":"9_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0890-5401(89)90044-8","volume":"83","author":"J.-S. Turner","year":"1989","unstructured":"J.-S. Turner, Approximation Algorithms for the Shortest Common Superstring Problem, Information and Computation\n83 (1989) 1\u201320.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60084-1_66.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:31:21Z","timestamp":1619573481000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60084-1_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540600848","9783540494256"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/3-540-60084-1_66","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}