{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:32:56Z","timestamp":1725557576315},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642135088"},{"type":"electronic","value":"9783642135095"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13509-5_20","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T09:19:57Z","timestamp":1277198397000},"page":"214-226","source":"Crossref","is-referenced-by-count":4,"title":["Extended Islands of Tractability for Parsimony Haplotyping"],"prefix":"10.1007","author":[{"given":"Rudolf","family":"Fleischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiong","family":"Guo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Uhlmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yihui","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xi","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"8","key":"20_CR1","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J.\u00a0Comput. System Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J.\u00a0Comput. System Sci."},{"issue":"5","key":"20_CR2","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1111\/j.1475-3995.2009.00716.x","volume":"16","author":"D. Catanzaro","year":"2009","unstructured":"Catanzaro, D., Labb\u00e9, M.: The pure parsimony haplotyping problem: Overview and computational advances. International Transactions in Operational Research\u00a016(5), 561\u2013584 (2009)","journal-title":"International Transactions in Operational Research"},{"unstructured":"Cicalese, F., Milani\u010d, M.: On parsimony haplotyping. Technical Report 2008-04, Universit\u00e4t Bielefeld (2008)","key":"20_CR3"},{"key":"20_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"20_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-642-02441-2_30","volume-title":"Combinatorial Pattern Matching","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hartman, T., Hermelin, D., Landau, G.M., Rosamond, F.A., Rozenberg, L.: Haplotype inference constrained by plausible haplotype data. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009. LNCS, vol.\u00a05577, pp. 339\u2013352. Springer, Heidelberg (2009)"},{"key":"20_CR6","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"20_CR7","first-page":"133","volume-title":"Proc. 40th STOC","author":"L. Fortnow","year":"2008","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for\u00a0NP. In: Proc. 40th STOC, pp. 133\u2013142. ACM Press, New York (2008)"},{"key":"20_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/978-3-540-28639-4_15","volume-title":"Parameterized and Exact Computation","author":"J. Guo","year":"2004","unstructured":"Guo, J., H\u00fcffner, F., Niedermeier, R.: A structural view on parameterizing problems: Distance from triviality. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol.\u00a03162, pp. 162\u2013173. Springer, Heidelberg (2004)"},{"issue":"1","key":"20_CR9","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News\u00a038(1), 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"key":"20_CR10","series-title":"CRC Handbook on Bioinformatics","first-page":"1","volume-title":"Haplotype inference","author":"D. Gusfield","year":"2005","unstructured":"Gusfield, D., Orzack, S.H.: Haplotype inference. CRC Handbook on Bioinformatics, ch.\u00a01, pp. 1\u201325. CRC Press, Boca Raton (2005)"},{"issue":"2","key":"20_CR11","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1109\/TCBB.2007.70232","volume":"5","author":"L. van Iersel","year":"2008","unstructured":"van Iersel, L., Keijsper, J., Kelk, S., Stougie, L.: Shorelines of islands of tractability: Algorithms for parsimony and minimum perfect phylogeny haplotyping problems. IEEE\/ACM Trans. Comput. Biology Bioinform.\u00a05(2), 301\u2013312 (2008)","journal-title":"IEEE\/ACM Trans. Comput. Biology Bioinform."},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-642-04128-0_31","volume-title":"Algorithms - ESA 2009","author":"G. J\u00e4ger","year":"2009","unstructured":"J\u00e4ger, G., Climer, S., Zhang, W.: Complete parsimony haplotype inference problem and algorithms. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 337\u2013348. Springer, Heidelberg (2009)"},{"issue":"4","key":"20_CR13","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1287\/ijoc.1040.0085","volume":"16","author":"G. Lancia","year":"2004","unstructured":"Lancia, G., Pinotti, M.C., Rizzi, R.: Haplotyping populations by pure parsimony: Complexity of exact and approximation algorithms. INFORMS Journal on Computing\u00a016(4), 348\u2013359 (2004)","journal-title":"INFORMS Journal on Computing"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.orl.2005.05.007","volume":"34","author":"G. Lancia","year":"2006","unstructured":"Lancia, G., Rizzi, R.: A polynomial case of the parsimony haplotyping problem. Operations Research Letters\u00a034, 289\u2013295 (2006)","journal-title":"Operations Research Letters"},{"key":"20_CR15","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"issue":"3","key":"20_CR16","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1109\/TCBB.2006.40","volume":"3","author":"R. Sharan","year":"2006","unstructured":"Sharan, R., Halld\u00f3rsson, B.V., Istrail, S.: Islands of tractability for parsimony haplotyping. IEEE\/ACM Trans. Comput. Biology Bioinform.\u00a03(3), 303\u2013311 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biology Bioinform."}],"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-13509-5_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:05:55Z","timestamp":1619784355000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13509-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642135088","9783642135095"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13509-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}