{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T12:15:26Z","timestamp":1785240926717,"version":"3.55.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,10,11]],"date-time":"2012-10-11T00:00:00Z","timestamp":1349913600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,10]]},"DOI":"10.1007\/s00453-012-9698-3","type":"journal-article","created":{"date-parts":[[2012,10,11]],"date-time":"2012-10-11T05:31:34Z","timestamp":1349933494000},"page":"142-160","source":"Crossref","is-referenced-by-count":5,"title":["FlipCut Supertrees: Towards Matrix Representation Accuracy in Polynomial Time"],"prefix":"10.1007","volume":"67","author":[{"given":"Malte","family":"Brinkmeyer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thasso","family":"Griebel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"B\u00f6cker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,10,11]]},"reference":[{"issue":"3","key":"9698_CR1","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"A.V. Aho","year":"1981","unstructured":"Aho, A.V., Sagiv, Y., Szymanski, T.G., Ullman, J.D.: Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. Comput. 10(3), 405\u2013421 (1981)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9698_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.2307\/1222480","volume":"41","author":"B.R. Baum","year":"1992","unstructured":"Baum, B.R.: Combining trees as a way of combining data sets for phylogenetic inference, and the desirability of combining gene trees. Taxon 41(1), 3\u201310 (1992)","journal-title":"Taxon"},{"key":"9698_CR3","series-title":"Computational Biology Series","volume-title":"Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life","year":"2004","unstructured":"Bininda-Emonds, O.R.P. (ed.): Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life. Computational Biology Series, vol.\u00a04. Kluwer Academic, Dordrecht (2004)"},{"key":"9698_CR4","doi-asserted-by":"crossref","first-page":"745","DOI":"10.1016\/S0076-6879(05)95038-6","volume":"395","author":"O.R.P. Bininda-Emonds","year":"2005","unstructured":"Bininda-Emonds, O.R.P.: Supertree construction in the genomic age. Methods Enzymol. 395, 745\u2013757 (2005)","journal-title":"Methods Enzymol."},{"key":"9698_CR5","unstructured":"B\u00f6cker, S., Bui, B., Nicolas, F., Truss, A.: Intractability of the minimum flip supertree problem and its variants. Technical report, Cornell University Library, arXiv:1112.4536v1 (2011)"},{"issue":"2","key":"9698_CR6","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/s00224-007-2010-2","volume":"41","author":"M. Brinkmeier","year":"2007","unstructured":"Brinkmeier, M.: A\u00a0simple and fast min-cut algorithm. Theory Comput. Syst. 41(2), 369\u2013380 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9698_CR7","doi-asserted-by":"crossref","DOI":"10.1155\/2011\/524182","volume":"2011","author":"M. Brinkmeyer","year":"2011","unstructured":"Brinkmeyer, M., Griebel, T., B\u00f6cker, S.: Polynomial supertree methods revisited. Adv. Bioinform. 2011, 524182 (2011)","journal-title":"Adv. Bioinform."},{"issue":"4","key":"9698_CR8","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1006\/aama.1995.1020","volume":"16","author":"D. Bryant","year":"1995","unstructured":"Bryant, D., Steel, M.A.: Extension operations on sets of leaf-labelled trees. Adv. Appl. Math. 16(4), 425\u2013453 (1995)","journal-title":"Adv. Appl. Math."},{"key":"9698_CR9","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1177\/117693430600200003","volume":"2","author":"D. Chen","year":"2006","unstructured":"Chen, D., Eulenstein, O., Fern\u00e1ndez-Baca, D., Burleigh, J.G.: Improved heuristics for minimum-flip supertree construction. Evol. Bioinform. 2, 347\u2013356 (2006)","journal-title":"Evol. Bioinform."},{"issue":"2","key":"9698_CR10","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1109\/TCBB.2006.26","volume":"3","author":"D. Chen","year":"2006","unstructured":"Chen, D., Eulenstein, O., Fern\u00e1ndez-Baca, D., Sanderson, M.: Minimum-flip supertrees: complexity and algorithms. IEEE\/ACM Trans. Comput. Biol. Bioinform. 3(2), 165\u2013173 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"9698_CR11","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1145\/1854776.1854800","volume-title":"Proc. of ACM Conf. on Bioinformatics and Computational Biology (ACM-BCB 2010)","author":"M. Chimani","year":"2010","unstructured":"Chimani, M., Rahmann, S., B\u00f6cker, S.: Exact ILP solutions for phylogenetic minimum flip problems. In: Proc. of ACM Conf. on Bioinformatics and Computational Biology (ACM-BCB 2010), pp.\u00a0147\u2013153. ACM, New York (2010)"},{"issue":"1","key":"9698_CR12","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0025-5564(86)90161-6","volume":"81","author":"W. Day","year":"1986","unstructured":"Day, W., Johnson, D., Sankoff, D.: The computational complexity of inferring rooted phylogenies by parsimony. Math. Biosci. 81(1), 33\u201342 (1986)","journal-title":"Math. Biosci."},{"key":"9698_CR13","volume-title":"Flows in Networks","author":"L.R. Ford","year":"1962","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"issue":"1","key":"9698_CR14","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"L. Foulds","year":"1982","unstructured":"Foulds, L., Graham, R.L.: The Steiner problem in phylogeny is NP-complete. Adv. Appl. Math. 3(1), 43\u201349 (1982)","journal-title":"Adv. Appl. Math."},{"key":"9698_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/BFb0045080","volume-title":"Proc. of Conference Computing and Combinatorics (COCOON 1997)","author":"L. Gasieniec","year":"1997","unstructured":"Gasieniec, L., Jansson, J., Lingas, A., \u00d6stlin, A.: On the complexity of computing evolutionary trees. In: Proc. of Conference Computing and Combinatorics (COCOON 1997). Lecture Notes in Computer Science, vol.\u00a01276, pp.\u00a0134\u2013145. Springer, Berlin (1997)"},{"key":"9698_CR16","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1023\/A:1009833626004","volume":"3","author":"L. Gasieniec","year":"1999","unstructured":"Gasieniec, L., Jansson, J., Lingas, A., \u00d6stlin, A.: On the complexity of constructing evolutionary trees. J. Comb. Optim. 3, 183\u2013197 (1999)","journal-title":"J. Comb. Optim."},{"issue":"20","key":"9698_CR17","doi-asserted-by":"crossref","first-page":"2399","DOI":"10.1093\/bioinformatics\/btn364","volume":"24","author":"T. Griebel","year":"2008","unstructured":"Griebel, T., Brinkmeyer, M., B\u00f6cker, S.: EPoS: a modular software framework for phylogenetic analysis. Bioinformatics 24(20), 2399\u20132400 (2008)","journal-title":"Bioinformatics"},{"issue":"1","key":"9698_CR18","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D. Gusfield","year":"1991","unstructured":"Gusfield, D.: Efficient algorithms for inferring evolutionary trees. Networks 21(1), 19\u201328 (1991)","journal-title":"Networks"},{"key":"9698_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"issue":"3","key":"9698_CR20","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1006\/jagm.1994.1043","volume":"17","author":"J.X. Hao","year":"1994","unstructured":"Hao, J.X., Orlin, J.B.: A\u00a0faster algorithm for finding the minimum cut in a directed graph. J.\u00a0Algorithms 17(3), 424\u2013446 (1994)","journal-title":"J.\u00a0Algorithms"},{"issue":"1","key":"9698_CR21","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/PL00009268","volume":"24","author":"M.R. Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V., Warnow, T.: Constructing a tree from homeomorphic subtrees with applications to computational evolutionary biology. Algorithmica 24(1), 13 (1999)","journal-title":"Algorithmica"},{"issue":"3\u20134","key":"9698_CR22","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1089\/106652799318337","volume":"6","author":"D.H. Huson","year":"1999","unstructured":"Huson, D.H., Nettles, S.M., Warnow, T.J.: Disk-covering, a fast-converging method for phylogenetic tree reconstruction. J.\u00a0Comput. Biol. 6(3\u20134), 369\u2013386 (1999)","journal-title":"J.\u00a0Comput. Biol."},{"key":"9698_CR23","first-page":"118","volume-title":"Proc. of Intelligent Systems for Molecular Biology (ISMB 1999)","author":"D.H. Huson","year":"1999","unstructured":"Huson, D.H., Vawter, L., Warnow, T.J.: Solving large scale phylogenetic problems using DCM2. In: Proc. of Intelligent Systems for Molecular Biology (ISMB 1999), pp.\u00a0118\u2013129 (1999)"},{"issue":"1","key":"9698_CR24","first-page":"46","volume":"47","author":"D.R. Karger","year":"2000","unstructured":"Karger, D.R.: Minimum cuts in near-linear time. J.\u00a0ACM 47(1), 46\u201376 (2000)","journal-title":"J.\u00a0ACM"},{"key":"9698_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1007\/3-540-45784-4_41","volume-title":"Proc. of Workshop on Algorithms in Bioinformatics (WABI 2002)","author":"R.D.M. Page","year":"2002","unstructured":"Page, R.D.M.: Modified mincut supertrees. In: Proc. of Workshop on Algorithms in Bioinformatics (WABI 2002). Lecture Notes in Computer Science, vol.\u00a02452, pp.\u00a0537\u2013552. Springer, Berlin (2002)"},{"issue":"3","key":"9698_CR26","doi-asserted-by":"crossref","first-page":"590","DOI":"10.1137\/S0097539702406510","volume":"33","author":"I. Pe\u2019er","year":"2004","unstructured":"Pe\u2019er, I., Pupko, T., Shamir, R., Sharan, R.: Incomplete directed perfect phylogeny. SIAM J. Comput. 33(3), 590\u2013607 (2004)","journal-title":"SIAM J. Comput."},{"key":"9698_CR27","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1007\/BFb0120902","volume":"13","author":"J.-C. Picard","year":"1980","unstructured":"Picard, J.-C., Queyranne, M.: On the structure of all minimum cuts in a network and applications. Math. Program. Stud. 13, 8\u201316 (1980)","journal-title":"Math. Program. Stud."},{"issue":"1","key":"9698_CR28","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/1055-7903(92)90035-F","volume":"1","author":"M.A. Ragan","year":"1992","unstructured":"Ragan, M.A.: Phylogenetic inference based on matrix representation of trees. Mol. Phylogenet. Evol. 1(1), 53\u201358 (1992)","journal-title":"Mol. Phylogenet. Evol."},{"issue":"5","key":"9698_CR29","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1080\/10635150701639754","volume":"56","author":"V. Ranwez","year":"2007","unstructured":"Ranwez, V., Berry, V., Criscuolo, A., Fabre, P.-H., Guillemot, S., Scornavacca, C., Douzery, E.J.P.: PhySIC: a veto supertree method with desirable properties. Syst. Biol. 56(5), 798\u2013817 (2007)","journal-title":"Syst. Biol."},{"issue":"12","key":"9698_CR30","doi-asserted-by":"crossref","first-page":"i115","DOI":"10.1093\/bioinformatics\/btq196","volume":"26","author":"V. Ranwez","year":"2010","unstructured":"Ranwez, V., Criscuolo, A., Douzery, E.J.P.: SuperTriplets: a triplet-based supertree approach to phylogenomics. Bioinformatics 26(12), i115\u2013i123 (2010)","journal-title":"Bioinformatics"},{"issue":"2","key":"9698_CR31","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1093\/sysbio\/45.2.247","volume":"45","author":"F. Ronquist","year":"1996","unstructured":"Ronquist, F.: Matrix representation of trees, redundancy, and weighting. Syst. Biol. 45(2), 247\u2013253 (1996)","journal-title":"Syst. Biol."},{"key":"9698_CR32","first-page":"98","volume-title":"Proc. of IEEE Computational Systems Bioinformatics Conference (CSB 2004)","author":"U. Roshan","year":"2004","unstructured":"Roshan, U., Moret, B., Warnow, T., Williams, T.: Rec-I-DCM3: a fast algorithmic technique for reconstructing large phylogenetic trees. In: Proc. of IEEE Computational Systems Bioinformatics Conference (CSB 2004), pp.\u00a098\u2013109 (2004)"},{"key":"9698_CR33","series-title":"Computational Biology Book Series","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-1-4020-2330-9_3","volume-title":"Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life","author":"H. Ross","year":"2004","unstructured":"Ross, H., Rodrigo, A.: An assessment of matrix representation with compatibility in supertree construction. In: Bininda-Emonds, O.R. (ed.) Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life. Computational Biology Book Series, vol.\u00a04, pp.\u00a035\u201363. Kluwer Academic, Dordrecht (2004)"},{"key":"9698_CR34","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1186\/1471-2105-9-413","volume":"9","author":"C. Scornavacca","year":"2008","unstructured":"Scornavacca, C., Berry, V., Lefort, V., Douzery, E.J.P., Ranwez, V.: PhySIC_IST: cleaning source trees to infer more informative supertrees. BMC Bioinform. 9, 413 (2008)","journal-title":"BMC Bioinform."},{"issue":"1\u20133","key":"9698_CR35","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0166-218X(00)00202-X","volume":"105","author":"C. Semple","year":"2000","unstructured":"Semple, C., Steel, M.: A\u00a0supertree method for rooted trees. Discrete Appl. Math. 105(1\u20133), 147\u2013158 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"21","key":"9698_CR36","doi-asserted-by":"crossref","first-page":"2688","DOI":"10.1093\/bioinformatics\/btl446","volume":"22","author":"A. Stamatakis","year":"2006","unstructured":"Stamatakis, A.: RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics 22(21), 2688\u20132690 (2006)","journal-title":"Bioinformatics"},{"issue":"2","key":"9698_CR37","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1093\/sysbio\/49.2.363","volume":"49","author":"M.A. Steel","year":"2000","unstructured":"Steel, M.A., Dress, A.W., B\u00f6cker, S.: Simple but fundamental limitations on supertree and consensus tree methods. Syst. Biol. 49(2), 363\u2013368 (2000)","journal-title":"Syst. Biol."},{"issue":"1","key":"9698_CR38","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1186\/1748-7188-5-8","volume":"5","author":"M.S. Swenson","year":"2010","unstructured":"Swenson, M.S., Barbancon, F., Warnow, T., Linder, C.R.: A\u00a0simulation study comparing supertree and combined analysis methods using SMIDGen. Algorithms Mol. Biol. 5(1), 8 (2010)","journal-title":"Algorithms Mol. Biol."},{"key":"9698_CR39","unstructured":"Swofford, D.L.: PAUP* Phylogenetic Analysis Using Parsimony (and Other Methods) 4.0 Beta. Sinauer Associates (2002)"},{"issue":"6","key":"9698_CR40","doi-asserted-by":"crossref","first-page":"1755","DOI":"10.1016\/j.bulm.2004.04.006","volume":"66","author":"S.J. Willson","year":"2004","unstructured":"Willson, S.J.: Constructing rooted supertrees using distances. Bull. Math. Biol. 66(6), 1755\u20131783 (2004)","journal-title":"Bull. Math. Biol."},{"issue":"3","key":"9698_CR41","doi-asserted-by":"crossref","first-page":"214","DOI":"10.2307\/2411550","volume":"14","author":"E.O. Wilson","year":"1965","unstructured":"Wilson, E.O.: A\u00a0consistency test for phylogenies based on contemporaneous species. Syst. Zool. 14(3), 214\u2013220 (1965)","journal-title":"Syst. Zool."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9698-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9698-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9698-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,4]],"date-time":"2019-07-04T15:37:26Z","timestamp":1562254646000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9698-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10,11]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["9698"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9698-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10,11]]}}}