{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:48:37Z","timestamp":1725482917911},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540716143"},{"type":"electronic","value":"9783540716150"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-71615-0_4","type":"book-chapter","created":{"date-parts":[[2007,4,18]],"date-time":"2007-04-18T18:51:34Z","timestamp":1176922294000},"page":"36-47","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Probabilistic Beam Search Approach to the Shortest Common Supersequence Problem"],"prefix":"10.1007","author":[{"given":"Christian","family":"Blum","sequence":"first","affiliation":[]},{"given":"Carlos","family":"Cotta","sequence":"additional","affiliation":[]},{"given":"Antonio J.","family":"Fern\u00e1ndez","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9 E.","family":"Gallardo","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Hallet, M.: An integrated complexity analysis of problems from computational biology. PhD thesis, University of Victoria (1996)"},{"issue":"1","key":"4_CR2","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S1570-8667(03)00011-X","volume":"1","author":"J. Sim","year":"2003","unstructured":"Sim, J., Park, K.: The consensus string problem for a metric is NP-complete. Journal of Discrete Algorithms\u00a01(1), 111\u2013117 (2003)","journal-title":"Journal of Discrete Algorithms"},{"issue":"2","key":"4_CR3","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1093\/bioinformatics\/btg1073","volume":"19","author":"S. Rahmann","year":"2003","unstructured":"Rahmann, S.: The shortest common supersequence problem in a microarray production setting. Bioinformatics\u00a019(Suppl. 2), ii156\u2013ii161 (2003)","journal-title":"Bioinformatics"},{"issue":"2-3","key":"4_CR4","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0004-3702(92)90016-Q","volume":"57","author":"D. Foulser","year":"1992","unstructured":"Foulser, D., Li, M., Yang, Q.: Theory and algorithms for plan merging. Artificial Intelligence\u00a057(2-3), 143\u2013181 (1992)","journal-title":"Artificial Intelligence"},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/BF01075212","volume":"25","author":"V. Timkovsky","year":"1990","unstructured":"Timkovsky, V.: Complexity of common subsequence and supersequence problems and related problems. Cybernetics\u00a025, 565\u2013580 (1990)","journal-title":"Cybernetics"},{"issue":"1\u20132","key":"4_CR6","first-page":"31","volume":"147","author":"H. Bodlaender","year":"1994","unstructured":"Bodlaender, H., Downey, R., Fellows, M., Wareham, H.: The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science\u00a0147(1\u20132), 31\u201354 (1994)","journal-title":"Theoretical Computer Science"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)00074-2","volume":"125","author":"M. Middendorf","year":"1994","unstructured":"Middendorf, M.: More on the complexity of common superstring and supersequence problems. Theoretical Computer Science\u00a0125, 205\u2013228 (1994)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"4_CR8","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1016\/S0022-0000(03)00078-3","volume":"67","author":"K. Pietrzak","year":"2003","unstructured":"Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences\u00a067(1), 757\u2013771 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/BF01545528","volume":"20","author":"J. Branke","year":"1998","unstructured":"Branke, J., Middendorf, M., Schneider, F.: Improved heuristics and a genetic algorithm for finding short supersequences. OR-Spektrum\u00a020, 39\u201345 (1998)","journal-title":"OR-Spektrum"},{"key":"4_CR10","unstructured":"Branke, J., Middendorf, M.: Searching for shortest common supersequences by means of a heuristic based genetic algorithm. In: Proceedings of the Second Nordic Workshop on Genetic Algorithms and their Applications, Finnish Artificial Intelligence Society, pp. 105\u2013114 (1996)"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/11494669_7","volume-title":"Computational Intelligence and Bioinspired Systems","author":"C. Cotta","year":"2005","unstructured":"Cotta, C.: A comparison of evolutionary approaches to the shortest common supersequence problem. In: Cabestany, J., Prieto, A.G., Sandoval, F. (eds.) IWANN 2005. LNCS, vol.\u00a03512, pp. 50\u201358. Springer, Heidelberg (2005)"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/11499305_9","volume-title":"Artificial Intelligence and Knowledge Engineering Applications: a Bioinspired Approach","author":"C. Cotta","year":"2005","unstructured":"Cotta, C.: Memetic algorithms with partial lamarckism for the shortest common supersequence problem. In: Mira, J., \u00c1lvarez, J. (eds.) Artificial Intelligence and Knowledge Engineering Applications: a Bioinspired Approach. LNCS, vol.\u00a03562, pp. 84\u201391. Springer, Heidelberg (2005)"},{"key":"4_CR13","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1998","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1998)"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/3-540-46784-X_30","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Chen","year":"1999","unstructured":"Chen, J., Kanj, I., Jia, W.: Vertex cover: further observations and further improvements. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG\u201999. LNCS, vol.\u00a01665, pp. 313\u2013324. Springer, Heidelberg (1999)"},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(00)00004-1","volume":"73","author":"R. Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parameter-tractable algorithms. Information Processing Letters\u00a073, 125\u2013129 (2000)","journal-title":"Information Processing Letters"},{"key":"4_CR16","first-page":"297","volume":"26","author":"P.S. Ow","year":"1988","unstructured":"Ow, P.S., Morton, T.E.: Filtered beam search in scheduling. International Journal of Production Research\u00a026, 297\u2013307 (1988)","journal-title":"International Journal of Production Research"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Gallardo, J.E., Cotta, C., Fern\u00e1ndez, A.J.: Hybridization of memetic algorithms with branch-and-bound techniques. In: IEEE Transactions on Systems, Man, and Cybernetics, Part B in press (2006)","DOI":"10.1109\/TSMCB.2006.883266"}],"container-title":["Lecture Notes in Computer Science","Evolutionary Computation in Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-71615-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T14:24:44Z","timestamp":1683815084000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-71615-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540716143","9783540716150"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-71615-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}