{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T18:40:19Z","timestamp":1792176019733,"version":"4.4.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2017,8,22]],"date-time":"2017-08-22T00:00:00Z","timestamp":1503360000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NWO VIDI"},{"name":"NWO TOP 2"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00453-017-0366-5","type":"journal-article","created":{"date-parts":[[2017,8,22]],"date-time":"2017-08-22T14:00:11Z","timestamp":1503410411000},"page":"2993-3022","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems"],"prefix":"10.1007","volume":"80","author":[{"given":"Leo","family":"van Iersel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steven","family":"Kelk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georgios","family":"Stamoulis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Olivier","family":"Boes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,8,22]]},"reference":[{"key":"366_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00026-001-8006-8","volume":"5","author":"BL Allen","year":"2001","unstructured":"Allen, B.L., Steel, M.: Subtree transfer operations and their induced metrics on evolutionary trees. Ann. Comb. 5, 1\u201315 (2001)","journal-title":"Ann. Comb."},{"key":"366_CR2","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s00285-005-0315-9","volume":"51","author":"M Baroni","year":"2005","unstructured":"Baroni, M., Gr\u00fcnewald, S., Moulton, V., Semple, C.: Bounding the number of hybridisation events for a consistent evolutionary history. Math. Biol. 51, 171\u2013182 (2005)","journal-title":"Math. Biol."},{"key":"366_CR3","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1177\/117693430700300017","volume":"3","author":"M Bordewich","year":"2007","unstructured":"Bordewich, M., Linz, S., St. John, K., Semple, C.: A reduction algorithm for computing the hybridization number of two trees. Evol. Bioinform. 3, 86\u201398 (2007)","journal-title":"Evol. Bioinform."},{"issue":"1\u20132","key":"366_CR4","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s00285-016-1023-3","volume":"74","author":"M Bordewich","year":"2017","unstructured":"Bordewich, M., Scornavacca, C., Tokac, N., Weller, M.: On the fixed parameter tractability of agreement-based phylogenetic distances. J. Math. Biol. 74(1\u20132), 239\u2013257 (2017)","journal-title":"J. Math. Biol."},{"issue":"3","key":"366_CR5","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1109\/tcbb.2007.1019","volume":"4","author":"M Bordewich","year":"2007","unstructured":"Bordewich, M., Semple, C.: Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable. IEEE\/ACM Trans. Comput. Biol. Bioinform. 4(3), 458\u2013466 (2007)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"8","key":"366_CR6","doi-asserted-by":"crossref","first-page":"914","DOI":"10.1016\/j.dam.2006.08.008","volume":"155","author":"M Bordewich","year":"2007","unstructured":"Bordewich, M., Semple, C.: Computing the minimum number of hybridization events for a consistent evolutionary history. Discrete Appl. Math. 155(8), 914\u2013928 (2007)","journal-title":"Discrete Appl. Math."},{"key":"366_CR7","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/j.aam.2016.04.004","volume":"78","author":"M Bordewich","year":"2016","unstructured":"Bordewich, M., Semple, C.: Reticulation-visible networks. Adv. Appl. Math. 78, 114\u2013141 (2016)","journal-title":"Adv. Appl. Math."},{"key":"366_CR8","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1016\/j.tcs.2014.10.031","volume":"562","author":"J Chen","year":"2015","unstructured":"Chen, J., Fan, J.-H., Sze, S.-H.: Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees. Theor. Comput. Sci. 562, 496\u2013512 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"366_CR9","doi-asserted-by":"crossref","first-page":"867","DOI":"10.1007\/s00453-015-0087-6","volume":"76","author":"J Chen","year":"2016","unstructured":"Chen, J., Shi, F., Wang, J.: Approximating maximum agreement forest on multiple binary trees. Algorithmica. 76(4), 867\u2013889 (2016)","journal-title":"Algorithmica."},{"key":"366_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity, vol. 4. Springer, New York (2013)"},{"issue":"3","key":"366_CR11","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1093\/sysbio\/syt108","volume":"63","author":"BT Drew","year":"2014","unstructured":"Drew, B.T., Ruhfel, B.R., Smith, S.A., Moore, M.J., Briggs, B.G., Gitzendanner, M.A., Soltis, P.S., Soltis, D.E.: Another look at the root of the angiosperms reveals a familiar tale. Syst. Biol. 63(3), 368\u2013382 (2014)","journal-title":"Syst. Biol."},{"key":"366_CR12","unstructured":"Felsenstein, J.: Inferring Phylogenies. Sinauer Associates, Incorporated (2004)"},{"issue":"4","key":"366_CR13","doi-asserted-by":"crossref","first-page":"1250004","DOI":"10.1142\/S0219720012500047","volume":"10","author":"P Gambette","year":"2012","unstructured":"Gambette, P., Berry, V., Paul, C.: Quartets and unrooted phylogenetic networks. J. Bioinform. Comput. Biol. 10(4), 1250004 (2012)","journal-title":"J. Bioinform. Comput. Biol."},{"issue":"1","key":"366_CR14","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1093\/comjnl\/bxm049","volume":"51","author":"J Gramm","year":"2008","unstructured":"Gramm, J., Nickelsen, A., Tantau, T.: Fixed-parameter algorithms in phylogenetics. Comput. J. 51(1), 79\u2013101 (2008)","journal-title":"Comput. J."},{"key":"366_CR15","unstructured":"Gunawan, A.D.M., DasGupta, B., Zhang, L.: Locating a phylogenetic tree in a reticulation-visible network in quadratic time. arXiv preprint arXiv:1603.08655 (2016)"},{"issue":"17","key":"366_CR16","doi-asserted-by":"crossref","first-page":"i503","DOI":"10.1093\/bioinformatics\/btw467","volume":"32","author":"Andreas DM Gunawan","year":"2016","unstructured":"Gunawan, Andreas D.M., Lu, Bingxin, Zhang, Louxin: A program for verification of phylogenetic network models. Bioinformatics 32(17), i503 (2016)","journal-title":"Bioinformatics"},{"key":"366_CR17","volume-title":"Phylogenetic Networks: Concepts, Algorithms and Applications","author":"DH Huson","year":"2011","unstructured":"Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press, Cambridge (2011)"},{"issue":"1","key":"366_CR18","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1093\/gbe\/evq077","volume":"3","author":"DH Huson","year":"2011","unstructured":"Huson, D.H., Scornavacca, C.: A survey of combinatorial methods for phylogenetic networks. Genome Biol. Evol. 3(1), 23\u201335 (2011)","journal-title":"Genome Biol. Evol."},{"issue":"6","key":"366_CR19","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1093\/sysbio\/sys062","volume":"61","author":"DH Huson","year":"2012","unstructured":"Huson, D.H., Scornavacca, C.: Dendroscope 3: an interactive tool for rooted phylogenetic trees and networks. Syst. Biol. 61(6), 1061\u20131067 (2012)","journal-title":"Syst. Biol."},{"key":"366_CR20","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.tcs.2008.04.019","volume":"401","author":"I Kanj","year":"2008","unstructured":"Kanj, I., Nakleh, L., Than, C., Xia, G.: Seeing the trees and their branches in the network is hard. Theor. Comput. Sci. 401, 153\u2013164 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"366_CR21","doi-asserted-by":"crossref","first-page":"886","DOI":"10.1007\/s00453-012-9708-5","volume":"68","author":"S Kelk","year":"2014","unstructured":"Kelk, S., Scornavacca, C.: Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable. Algorithmica 68(4), 886\u2013915 (2014)","journal-title":"Algorithmica"},{"issue":"4","key":"366_CR22","doi-asserted-by":"crossref","first-page":"1635","DOI":"10.1137\/120864350","volume":"26","author":"S Kelk","year":"2012","unstructured":"Kelk, S., van Iersel, L.J.J., Linz, S., Leki\u0107, N., Scornavacca, C., Stougie, L.: Cycle killer... Qu\u2019est-ce que c\u2019est? On the comparative approximability of hybridization number and directed feedback vertex set. SIAM J. Discrete Math. SIDMA 26(4), 1635\u20131656 (2012)","journal-title":"SIAM J. Discrete Math. SIDMA"},{"key":"366_CR23","volume-title":"An Introduction to Phylogenetic Networks","author":"DA Morrison","year":"2011","unstructured":"Morrison, D.A.: An Introduction to Phylogenetic Networks. RJR Productions, Uppsala (2011)"},{"key":"366_CR24","doi-asserted-by":"crossref","unstructured":"Nakhleh, L.: Evolutionary phylogenetic networks: models and issues. In: Heath, L.S., Ramakrishnan, N. (eds.) Problem Solving Handbook in Computational Biology and Bioinformatics, No. 784. Springer Science & Business Media (2010)","DOI":"10.1007\/978-0-387-09760-2_7"},{"issue":"3","key":"366_CR25","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"366_CR26","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1109\/TC.1984.1676428","volume":"3","author":"D Richards","year":"1984","unstructured":"Richards, D.: Complexity of single-layer routing. IEEE Trans. Comput. 3, 286\u2013288 (1984)","journal-title":"IEEE Trans. Comput."},{"key":"366_CR27","volume-title":"The Phylogenetic Handbook. A Practical Approach to DNA and Protein Phylogeny","year":"2003","unstructured":"Salemi, M., Vandamme, A.M. (eds.): The Phylogenetic Handbook. A Practical Approach to DNA and Protein Phylogeny. Cambridge University Press, Cambridge (2003)"},{"key":"366_CR28","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2002","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, New York (2002)"},{"key":"366_CR29","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)"},{"key":"366_CR30","first-page":"127","volume":"15","author":"LJJ Iersel van","year":"2013","unstructured":"van Iersel, L.J.J., Kelk, S., Leki\u0107, N., Scornavacca, C.: A practical approximation algorithm for solving massive instances of hybridization number for binary and nonbinary trees. BMC Bioinform. 15, 127\u2013127 (2013)","journal-title":"BMC Bioinform."},{"issue":"6","key":"366_CR31","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1016\/j.jcss.2016.03.006","volume":"82","author":"LJJ Iersel van","year":"2016","unstructured":"van Iersel, L.J.J., Kelk, S., Scornavacca, C.: Kernelizations for the hybridization number problem on multiple nonbinary trees. J. Comput. Syst. Sci. 82(6), 1075\u20131089 (2016)","journal-title":"J. Comput. Syst. Sci."},{"issue":"9","key":"366_CR32","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1016\/j.ipl.2013.02.010","volume":"113","author":"LJJ Iersel van","year":"2013","unstructured":"van Iersel, L.J.J., Linz, S.: A quadratic kernel for computing the hybridization number of multiple trees. Inf. Process. Lett. 113(9), 318\u2013323 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"23","key":"366_CR33","doi-asserted-by":"crossref","first-page":"1037","DOI":"10.1016\/j.ipl.2010.07.027","volume":"110","author":"LJJ Iersel van","year":"2010","unstructured":"van Iersel, L.J.J., Semple, C., Steel, M.: Locating a tree in a phylogenetic network. Inf. Process. Lett. 110(23), 1037\u20131043 (2010)","journal-title":"Inf. Process. Lett."},{"key":"366_CR34","first-page":"296","volume":"265","author":"JF Wendel","year":"1998","unstructured":"Wendel, J.F., Doyle, J.J.: Phylogenetic incongruence: window into genome history and molecular evolution. Mol. Syst. Plants II DNA Seq. 265, 296 (1998)","journal-title":"Mol. Syst. Plants II DNA Seq."},{"issue":"4","key":"366_CR35","doi-asserted-by":"crossref","first-page":"1431","DOI":"10.1137\/110845045","volume":"42","author":"C Whidden","year":"2013","unstructured":"Whidden, C., Beiko, R.G., Zeh, N.: Fixed-parameter algorithms for maximum agreement forests. SIAM J. Comput. 42(4), 1431\u20131466 (2013)","journal-title":"SIAM J. Comput."},{"key":"366_CR36","first-page":"390","volume-title":"Algorithms in Bioinformatics, Volume 5724 of Lecture Notes in Computer Science","author":"C Whidden","year":"2009","unstructured":"Whidden, C., Zeh, N.: A unifying view on approximation and FPT of agreement forests. In: Salzberg, S.L., Warnow, T. (eds.) Algorithms in Bioinformatics, Volume 5724 of Lecture Notes in Computer Science, pp. 390\u2013402. Springer, Berlin (2009)"},{"issue":"4","key":"366_CR37","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1093\/sysbio\/syu023","volume":"63","author":"C Whidden","year":"2014","unstructured":"Whidden, C., Zeh, N., Beiko, R.G.: Supertrees based on the subtree prune-and-regraft distance. Syst. Biol. 63(4), 566\u2013581 (2014)","journal-title":"Syst. Biol."},{"issue":"4","key":"366_CR38","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1093\/sysbio\/syv020","volume":"64","author":"EW Wilberg","year":"2015","unstructured":"Wilberg, E.W.: What\u2019s in an outgroup? The impact of outgroup choice on the phylogenetic position of thalattosuchia (crocodylomorpha) and the origin of crocodyliformes. Syst. Biol. 64(4), 621\u2013637 (2015)","journal-title":"Syst. Biol."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0366-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0366-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0366-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,26]],"date-time":"2024-06-26T12:11:47Z","timestamp":1719403907000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0366-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,22]]},"references-count":38,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["366"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0366-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,22]]}}}