{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:18:52Z","timestamp":1725567532050},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642163203"},{"type":"electronic","value":"9783642163210"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16321-0_28","type":"book-chapter","created":{"date-parts":[[2010,10,5]],"date-time":"2010-10-05T14:51:32Z","timestamp":1286290292000},"page":"270-278","source":"Crossref","is-referenced-by-count":4,"title":["On Shortest Common Superstring and Swap Permutations"],"prefix":"10.1007","author":[{"given":"Zvi","family":"Gotthilf","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandru","family":"Popa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"28_CR1","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1006\/jagm.2000.1120","volume":"37","author":"A. Amir","year":"2000","unstructured":"Amir, A., Aumann, Y., Landau, G.M., Lewenstein, M., Lewenstein, N.: Pattern matching with swaps. J. Algorithms\u00a037(2), 247\u2013266 (2000)","journal-title":"J. Algorithms"},{"issue":"1","key":"28_CR2","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s00453-005-1192-8","volume":"45","author":"A. Amir","year":"2006","unstructured":"Amir, A., Eisenberg, E., Porat, E.: Swap and mismatch edit distance. Algorithmica\u00a045(1), 109\u2013120 (2006)","journal-title":"Algorithmica"},{"issue":"3","key":"28_CR3","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(98)00151-3","volume":"68","author":"A. Amir","year":"1998","unstructured":"Amir, A., Landau, G.M., Lewenstein, M., Lewenstein, N.: Efficient special cases of pattern matching with swaps. Inf. Process. Lett.\u00a068(3), 125\u2013132 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"28_CR4","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0020-0190(01)00302-7","volume":"83","author":"A. Amir","year":"2002","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Approximate swapped matching. Inf. Process. Lett.\u00a083(1), 33\u201339 (2002)","journal-title":"Inf. Process. Lett."},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Antoniou, P., Iliopoulos, C.S., Jayasekera, I., Sohel Rahman, M.: Implementation of a swap matching algorithm using a graph theoretic model. In: BIRD, pp. 446\u2013455 (2008)","DOI":"10.1007\/978-3-540-70600-7_34"},{"key":"28_CR6","unstructured":"Ardila, Y.J.P., Iliopoulos, C.S., Landau, G.M., Mohamed, M.: Approximation algorithm for the cyclic swap problem. In: Stringology, pp. 190\u2013200 (2005)"},{"issue":"4","key":"28_CR7","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1145\/179812.179818","volume":"41","author":"A. Blum","year":"1994","unstructured":"Blum, A., Jiang, T., Li, M., Tromp, J., Yannakakis, M.: Linear approximation of shortest superstrings. J. ACM\u00a041(4), 630\u2013647 (1994)","journal-title":"J. ACM"},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"Clifford, R., Gotthilf, Z., Lewenstein, M., Popa, A.: Restricted common superstring and restricted common supersequence. CoRR, abs\/1004.0424v2 (2010)","DOI":"10.1007\/978-3-642-21458-5_39"},{"key":"28_CR9","volume-title":"Computers and intractability. A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman, New York (1979)"},{"key":"28_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1007\/3-540-45678-3_61","volume-title":"Algorithms and Computation","author":"H. Hori","year":"2001","unstructured":"Hori, H., Shimozono, S., Takeda, M., Shinohara, A.: Fragmentary pattern matching: Complexity, algorithms and applications for analyzing classic literary works. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223, pp. 719\u2013730. Springer, Heidelberg (2001)"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"Iliopoulos, C.S., Sohel Rahman, M.: A new model to solve the swap matching problem and efficient algorithms for short patterns. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 316\u2013327. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-77566-9_27"},{"issue":"4","key":"28_CR12","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1145\/1082036.1082041","volume":"52","author":"H. Kaplan","year":"2005","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric tsp by decomposing directed regular multigraphs. J. ACM\u00a052(4), 602\u2013626 (2005)","journal-title":"J. ACM"},{"issue":"2","key":"28_CR13","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput.\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"28_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-46784-X_7","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Ott","year":"1999","unstructured":"Ott, S.: Lower bounds for approximating shortest superstrings over an alphabet of size 2. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, pp. 55\u201364. Springer, Heidelberg (1999)"},{"key":"28_CR15","unstructured":"Sacerdoti, E.D.: A structure for plans and behavior. American Elsevier (1977)"},{"issue":"3","key":"28_CR16","doi-asserted-by":"publisher","first-page":"954","DOI":"10.1137\/S0097539796324661","volume":"29","author":"Z. Sweedyk","year":"1999","unstructured":"Sweedyk, Z.: A 2 $\\frac{1}{2}$ -approximation algorithm for shortest superstring. SIAM J. Comput.\u00a029(3), 954\u2013986 (1999)","journal-title":"SIAM J. Comput."},{"key":"28_CR17","unstructured":"Tate, A.: Generating project networks. In: IJCAI, pp. 888\u2013893 (1977)"},{"issue":"3","key":"28_CR18","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica\u00a014(3), 249\u2013260 (1995)","journal-title":"Algorithmica"},{"key":"28_CR19","volume-title":"Practical planning: Extending the classical ai planning paradigm","author":"D.E. Wilkins","year":"1988","unstructured":"Wilkins, D.E.: Practical planning: Extending the classical ai planning paradigm. Morgan Kaufmann, CA (1988)"},{"key":"28_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1007\/978-3-540-30497-5_109","volume-title":"Computational and Information Science","author":"H. Zhang","year":"2004","unstructured":"Zhang, H., Guo, Q., Iliopoulos, C.S.: String matching with swaps in a weighted sequence. In: Zhang, J., He, J.-H., Fu, Y. (eds.) CIS 2004. LNCS, vol.\u00a03314, pp. 698\u2013704. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16321-0_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T07:13:21Z","timestamp":1559718801000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16321-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642163203","9783642163210"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16321-0_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}