{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T03:27:54Z","timestamp":1725593274843},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642214578"},{"type":"electronic","value":"9783642214585"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-21458-5_39","type":"book-chapter","created":{"date-parts":[[2011,6,27]],"date-time":"2011-06-27T21:11:27Z","timestamp":1309209087000},"page":"467-478","source":"Crossref","is-referenced-by-count":5,"title":["Restricted Common Superstring and Restricted Common Supersequence"],"prefix":"10.1007","author":[{"given":"Rapha\u00ebl","family":"Clifford","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zvi","family":"Gotthilf","sequence":"additional","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":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"Barone, P., Bonizzoni, P., Vedova, G.D., Mauri, G.: An approximation algorithm for the shortest common supersequence problem: an experimental analysis. In: Symposium on Applied Computing, pp. 56\u201360 (2001)","DOI":"10.1145\/372202.372275"},{"key":"39_CR2","unstructured":"Berger, B., Peter, W.S.: Approximation algorithms for the maximum acyclic subgraph problem. In: SODA, pp. 236\u2013243 (1990)"},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"Bl\u00e4ser, M.: A 3\/4-approximation algorithm for maximum atsp with weights zero and one. In: APPROX-RANDOM, pp. 61\u201371 (2004)","DOI":"10.1007\/978-3-540-27821-4_6"},{"issue":"4","key":"39_CR4","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":"39_CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guruswami, V., Manokaran, R.: Every permutation csp of arity 3 is approximation resistant. In: IEEE Conference on Computational Complexity, pp. 62\u201373 (2009)","DOI":"10.1109\/CCC.2009.29"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Cotta, C.: Memetic algorithms with partial lamarckism for the shortest common supersequence problem. In: IWINAC, vol.\u00a0(2), pp. 84\u201391 (2005)","DOI":"10.1007\/11499305_9"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Engebretsen, L., Karpinski, M.: Approximation hardness of tsp with bounded metrics. In: ICALP, pp. 201\u2013212 (2001)","DOI":"10.1007\/3-540-48224-5_17"},{"key":"39_CR8","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":"39_CR9","doi-asserted-by":"crossref","unstructured":"Gotthilf, Z., Lewenstein, M.: Improved approximation results on the shortest common supersequence problem. In: SPIRE, pp. 277\u2013284 (2009)","DOI":"10.1007\/978-3-642-03784-9_27"},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"Gotthilf, Z., Lewenstein, M., Popa, A.: On shortest common superstring and swap permutations. In: SPIRE, pp. 270\u2013278 (2010)","DOI":"10.1007\/978-3-642-16321-0_28"},{"key":"39_CR11","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Manokaran, R., Raghavendra, P.: Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In: FOCS, pp. 573\u2013582 (2008)","DOI":"10.1109\/FOCS.2008.51"},{"issue":"5","key":"39_CR12","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T. Jiang","year":"1995","unstructured":"Jiang, T., Li, M.: On the approximation of shortest common supersequences and longest common subsequences. SIAM J. Comput.\u00a024(5), 1122\u20131139 (1995)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"39_CR13","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":"39_CR14","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM\u00a025(2), 322\u2013336 (1978)","journal-title":"J. ACM"},{"issue":"2","key":"39_CR15","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0304-3975(93)90200-D","volume":"108","author":"M. Middendorf","year":"1993","unstructured":"Middendorf, M.: The shortest common nonsubsequence problem is NP-complete. Theor. Comput. Sci.\u00a0108(2), 365\u2013369 (1993)","journal-title":"Theor. Comput. Sci."},{"key":"39_CR16","doi-asserted-by":"crossref","unstructured":"Ott, S.: Lower bounds for approximating shortest superstrings over an alphabet of size 2. In: WG, pp. 55\u201364 (1999)","DOI":"10.1007\/3-540-46784-X_7"},{"issue":"3","key":"39_CR17","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci.\u00a043(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"39_CR18","doi-asserted-by":"publisher","first-page":"1763","DOI":"10.1137\/0152101","volume":"52","author":"P.A. Pevzner","year":"1992","unstructured":"Pevzner, P.A.: Multiple alignment, communication cost, and graph matching. SIAM Journal of Applied Mathematics\u00a052(6), 1763\u20131779 (1992)","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"39_CR19","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0304-3975(81)90075-X","volume":"16","author":"K.-J. R\u00e4ih\u00e4","year":"1981","unstructured":"R\u00e4ih\u00e4, K.-J., Ukkonen, E.: The shortest common supersequence problem over binary alphabet is NP-complete. Theor. Comput. Sci.\u00a016, 187\u2013198 (1981)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"39_CR20","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/S0895480192234277","volume":"11","author":"A.R. Rubinov","year":"1998","unstructured":"Rubinov, A.R., Timkovsky, V.G.: String noninclusion optimization problems. SIAM J. Discrete Math.\u00a011(3), 456\u2013467 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"39_CR21","volume-title":"A structure for plans and behavior","author":"E.D. Sacerdoti","year":"1977","unstructured":"Sacerdoti, E.D.: A structure for plans and behavior. Elsevier, Amsterdam (1977)"},{"key":"39_CR22","volume-title":"Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison","author":"D. Sankoff","year":"1983","unstructured":"Sankoff, D., Kruskal, J.: Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. CSLI Publications, Stanford (1983)"},{"issue":"1","key":"39_CR23","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/42201.42203","volume":"13","author":"T.K. Sellis","year":"1988","unstructured":"Sellis, T.K.: Multiple-query optimization. ACM Trans. Database Syst.\u00a013(1), 23\u201352 (1988)","journal-title":"ACM Trans. Database Syst."},{"key":"39_CR24","volume-title":"Data Compression: Methods and Theory","author":"J.A. Storer","year":"1988","unstructured":"Storer, J.A.: Data Compression: Methods and Theory. Computer Science Press, Rockville (1988)"},{"issue":"3","key":"39_CR25","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":"39_CR26","unstructured":"Tate, A.: Generating project networks. In: IJCAI, pp. 888\u2013893 (1977)"},{"key":"39_CR27","doi-asserted-by":"crossref","unstructured":"Timkovsky, V.G.: Some approximations for shortest common nonsubsequences and supersequences. In: SPIRE, pp. 257\u2013268 (2008)","DOI":"10.1007\/978-3-540-89097-3_25"},{"key":"39_CR28","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2004","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2004)"},{"key":"39_CR29","volume-title":"Planning and understanding","author":"R. Wilensky","year":"1983","unstructured":"Wilensky, R.: Planning and understanding. Addison-Wesley, Reading (1983)"},{"key":"39_CR30","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, San Francisco (1988)"},{"issue":"1","key":"39_CR31","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing\u00a03(1), 103\u2013128 (2007)","journal-title":"Theory of Computing"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21458-5_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T12:04:46Z","timestamp":1560341086000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21458-5_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642214578","9783642214585"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21458-5_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}