{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T03:27:52Z","timestamp":1725593272419},"publisher-location":"Berlin, Heidelberg","reference-count":11,"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_29","type":"book-chapter","created":{"date-parts":[[2011,6,27]],"date-time":"2011-06-27T21:11:27Z","timestamp":1309209087000},"page":"336-349","source":"Crossref","is-referenced-by-count":2,"title":["Tractability and Approximability of Maximal Strip Recovery"],"prefix":"10.1007","author":[{"given":"Laurent","family":"Bulteau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Fertin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minghui","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irena","family":"Rusu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1007\/978-3-642-10631-6_72","volume-title":"Algorithms and Computation","author":"L. Bulteau","year":"2009","unstructured":"Bulteau, L., Fertin, G., Rusu, I.: Maximal strip recovery problem with gaps: Hardness and approximation algorithms. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 710\u2013719. Springer, Heidelberg (2009)"},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10878-009-9233-x","volume":"18","author":"Z. Chen","year":"2009","unstructured":"Chen, Z., Fu, B., Jiang, M., Zhu, B.: On recovering syntenic blocks from comparative maps. Journal of Combinatorial Optimization\u00a018, 307\u2013318 (2009)","journal-title":"Journal of Combinatorial Optimization"},{"key":"29_CR3","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/978-3-540-74126-8_26","volume-title":"Algorithms in Bioinformatics","author":"V. Choi","year":"2007","unstructured":"Choi, V., Zheng, C., Zhu, Q., Sankoff, D.: Algorithms for the extraction of synteny blocks from comparative maps. In: Giancarlo, R., Hannenhalli, S. (eds.) WABI 2007. LNCS (LNBI), vol.\u00a04645, pp. 277\u2013288. Springer, Heidelberg (2007)"},{"key":"29_CR4","unstructured":"Halld\u00f3rsson, M.M.: Approximating discrete collections via local improvements. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1995), pp. 160\u2013169 (1995)"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Jiang, H., Li, Z., Lin, G., Wang, L., Zhu, B.: Exact and approximation algorithms for the complementary maximal strip recovery problem. In: Journal of Combinatorial Optimization (to appear), doi:10.1007\/s10878-010-9366-y","DOI":"10.1007\/s10878-010-9366-y"},{"key":"29_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1007\/978-3-642-10631-6_63","volume-title":"Algorithms and Computation","author":"M. Jiang","year":"2009","unstructured":"Jiang, M.: Inapproximability of maximal strip recovery. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 616\u2013625. Springer, Heidelberg (2009)"},{"key":"29_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-642-13509-5_12","volume-title":"Combinatorial Pattern Matching","author":"M. Jiang","year":"2010","unstructured":"Jiang, M.: On the parameterized complexity of some optimization problems related to multiple-interval graphs. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 125\u2013137. Springer, Heidelberg (2010)"},{"key":"29_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-642-14553-7_8","volume-title":"Frontiers in Algorithmics","author":"M. Jiang","year":"2010","unstructured":"Jiang, M.: Inapproximability of maximal strip recovery: II. In: Lee, D.-T., Chen, D.Z., Ying, S. (eds.) FAW 2010. LNCS, vol.\u00a06213, pp. 53\u201364. Springer, Heidelberg (2010)"},{"key":"29_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/978-3-642-02017-9_42","volume-title":"Theory and Applications of Models of Computation","author":"L. Wang","year":"2009","unstructured":"Wang, L., Zhu, B.: On the tractability of maximal strip recovery. In: Chen, J., Cooper, S.B. (eds.) TAMC 2009. LNCS, vol.\u00a05532, pp. 400\u2013409. Springer, Heidelberg (2009)"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1109\/TCBB.2007.1075","volume":"4","author":"C. Zheng","year":"2007","unstructured":"Zheng, C., Zhu, Q., Sankoff, D.: Removing noise and ambiguities from comparative maps in rearrangement analysis. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a04, 515\u2013522 (2007)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"key":"29_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-642-14355-7_33","volume-title":"Algorithmic Aspects in Information and Management","author":"B. Zhu","year":"2010","unstructured":"Zhu, B.: Efficient exact and approximate algorithms for the complement of maximal strip recovery. In: Chen, B. (ed.) AAIM 2010. LNCS, vol.\u00a06124, pp. 325\u2013333. Springer, Heidelberg (2010)"}],"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_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T13:54:50Z","timestamp":1553867690000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21458-5_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642214578","9783642214585"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21458-5_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}