{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:51:26Z","timestamp":1742395886615},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642276590"},{"type":"electronic","value":"9783642276606"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":[[2012]]},"DOI":"10.1007\/978-3-642-27660-6_13","type":"book-chapter","created":{"date-parts":[[2012,1,16]],"date-time":"2012-01-16T10:14:28Z","timestamp":1326708868000},"page":"153-164","source":"Crossref","is-referenced-by-count":2,"title":["Complexity Insights of the Minimum Duplication Problem"],"prefix":"10.1007","author":[{"given":"Guillaume","family":"Blin","sequence":"first","affiliation":[]},{"given":"Paola","family":"Bonizzoni","sequence":"additional","affiliation":[]},{"given":"Riccardo","family":"Dondi","sequence":"additional","affiliation":[]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"13_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theoretical Comput. Sci.\u00a0237(1-2), 123\u2013134 (2000)","journal-title":"Theoretical Comput. Sci."},{"key":"13_CR2","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-540-71681-5_17","volume-title":"Research in Computational Molecular Biology","author":"M.S. Bansal","year":"2007","unstructured":"Bansal, M.S., Burleigh, J.G., Eulenstein, O., Wehe, A.: Heuristics for the Gene-Duplication Problem: A \u0398(n) Speed-Up for the Local Search. In: Speed, T.P., Huang, H. (eds.) RECOMB 2007. LNCS (LNBI), vol.\u00a04453, pp. 238\u2013252. Springer, Heidelberg (2007)"},{"issue":"2","key":"13_CR3","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1109\/TCBB.2009.7","volume":"6","author":"M.S. Bansal","year":"2009","unstructured":"Bansal, M.S., Eulenstein, O., Wehe, A.: The Gene-Duplication Problem: Near-Linear Time Algorithms for NNI-Based Local Searches. IEEE\/ACM Trans. Comput. Biology Bioinform.\u00a06(2), 221\u2013231 (2009)","journal-title":"IEEE\/ACM Trans. Comput. Biology Bioinform."},{"issue":"3","key":"13_CR4","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1109\/TCBB.2010.74","volume":"8","author":"M.S. Bansal","year":"2011","unstructured":"Bansal, M.S., Shamir, R.: A Note on the Fixed Parameter Tractability of the Gene-Duplication Problem. IEEE\/ACM Transactions on Computational Biology and Bioinformatics (TCBB)\u00a08(3), 848\u2013850 (2011)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics (TCBB)"},{"issue":"11","key":"13_CR5","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1016\/j.dam.2010.03.004","volume":"158","author":"J. Byrka","year":"2010","unstructured":"Byrka, J., Guillemot, S., Jansson, J.: New results on optimizing rooted triplets consistency. Discrete Appl. Math.\u00a0158(11), 1136\u20131147 (2010)","journal-title":"Discrete Appl. Math."},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Chang, W.-C., Burleigh, J.G., Fern\u00e1ndez-Baca, D.F., Eulenstein, O.: An ILP solution for the gene duplication problem. BMC Bioinformatics (suppl. 1), S14(12) (2011)","DOI":"10.1186\/1471-2105-12-S1-S14"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/978-3-642-02008-7_4","volume-title":"Research in Computational Molecular Biology","author":"C. Chauve","year":"2009","unstructured":"Chauve, C., El-Mabrouk, N.: New Perspectives on Gene Family Evolution: Losses in Reconciliation and a Link with Supertrees. In: Batzoglou, S. (ed.) RECOMB 2009. LNCS, vol.\u00a05541, pp. 46\u201358. Springer, Heidelberg (2009)"},{"issue":"5634","key":"13_CR8","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1126\/science.1086132","volume":"301","author":"E.F. Eichler","year":"2003","unstructured":"Eichler, E.F., Sankoff, D.: Structural dynamics of eukaryotic chromosome evolution. Science\u00a0301(5634), 521\u2013565 (2003)","journal-title":"Science"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1146\/annurev.ge.22.120188.002513","volume":"22","author":"J. Felsenstein","year":"1988","unstructured":"Felsenstein, J.: Phylogenies from molecular sequences: Inference and reliability. Ann. Review Genet.\u00a022, 521\u2013565 (1988)","journal-title":"Ann. Review Genet."},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0168-9525(00)02005-9","volume":"16","author":"W.M. Fitch","year":"2000","unstructured":"Fitch, W.M.: Homology a personal view on some of the problems. Trends Genet.\u00a016, 227\u2013231 (2000)","journal-title":"Trends Genet."},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Hallett, M.T., Lagergren, J.: New algorithms for the duplication-loss model. In: RECOMB, pp. 138\u2013146 (2000)","DOI":"10.1145\/332306.332359"},{"key":"13_CR12","unstructured":"Kleinberg, J., Tardos, E.: Algorithm Design. Pearson Education (2006)"},{"issue":"3","key":"13_CR13","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1137\/S0097539798343362","volume":"30","author":"B. Ma","year":"2000","unstructured":"Ma, B., Li, M., Zhang, L.: From Gene Trees to Species Trees. SIAM J. Comput.\u00a030(3), 729\u2013752 (2000)","journal-title":"SIAM J. Comput."},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/978-3-642-16181-0_24","volume-title":"Comparative Genomics","author":"A. Ouangraoua","year":"2010","unstructured":"Ouangraoua, A., Swenson, K.M., Chauve, C.: An Approximation Algorithm for Computing a Parsimonious First Speciation in the Gene Duplication Model. In: Tannier, E. (ed.) RECOMB-CG 2010. LNCS, vol.\u00a06398, pp. 290\u2013301. Springer, Heidelberg (2010)"},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-48447-7_29","volume-title":"Algorithms and Data Structures","author":"U. Stege","year":"1999","unstructured":"Stege, U.: Gene Trees and Species Trees: The Gene-Duplication Problem in Fixed-Parameter Tractable. In: Dehne, F.K.H.A., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 288\u2013293. Springer, Heidelberg (1999)"},{"issue":"1","key":"13_CR16","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1093\/comjnl\/10.1.85","volume":"10","author":"D.J.A. Welsh","year":"1967","unstructured":"Welsh, D.J.A., Powell, M.B.: An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal\u00a010(1), 85\u201386 (1967)","journal-title":"The Computer Journal"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2012: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-27660-6_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T19:49:39Z","timestamp":1556135379000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-27660-6_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642276590","9783642276606"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-27660-6_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}