{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:11:47Z","timestamp":1761621107148},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,6,26]],"date-time":"2012-06-26T00:00:00Z","timestamp":1340668800000},"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":[[2014,1]]},"DOI":"10.1007\/s00453-012-9663-1","type":"journal-article","created":{"date-parts":[[2012,6,25]],"date-time":"2012-06-25T14:44:01Z","timestamp":1340635441000},"page":"81-108","source":"Crossref","is-referenced-by-count":3,"title":["A Cubic-Vertex Kernel for Flip Consensus Tree"],"prefix":"10.1007","volume":"68","author":[{"given":"Christian","family":"Komusiewicz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Uhlmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,6,26]]},"reference":[{"key":"9663_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/11847250_24","volume-title":"Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC\u00a0\u201906)","author":"F.N. Abu-Khzam","year":"2006","unstructured":"Abu-Khzam, F.N., Fernau, H.: Kernels: Annotated, proper and induced. In: Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC\u00a0\u201906). Lecture Notes in Computer Science, vol. 4169, pp. 264\u2013275. Springer, Berlin (2006)"},{"issue":"16","key":"9663_CR2","doi-asserted-by":"crossref","first-page":"1732","DOI":"10.1016\/j.dam.2010.07.002","volume":"158","author":"S. Bessy","year":"2010","unstructured":"Bessy, S., Paul, C., Perez, A.: Polynomial kernels for 3-leaf power graph modification problems. Discrete Appl. Math. 158(16), 1732\u20131744 (2010)","journal-title":"Discrete Appl. Math."},{"key":"9663_CR3","volume-title":"Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life","year":"2004","unstructured":"Bininda-Emonds, O. (ed.): Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life. Kluwer Academic, Dordrecht (2004)"},{"key":"9663_CR4","unstructured":"B\u00f6cker, S., Bui, Q.B.A., Nicolas, F., Truss, A.: Intractability of the minimum-flip supertree problem and its variants. Technical report, Cornell University Library (2011). arXiv: 1112.4536v1"},{"issue":"1","key":"9663_CR5","doi-asserted-by":"crossref","first-page":"7:1","DOI":"10.1145\/2071379.2071386","volume":"8","author":"S. B\u00f6cker","year":"2012","unstructured":"B\u00f6cker, S., Bui, Q.B.A., Truss, A.: Improved fixed-parameter algorithms for minimum-flip consensus trees. ACM Trans. Algorithms 8(1), 7:1\u20137:17 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"9663_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/978-3-642-11269-0_2","volume-title":"Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC\u00a0\u201909)","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC\u00a0\u201909). Lecture Notes in Computer Science, vol. 5917, pp. 17\u201337. Springer, Berlin (2009)"},{"issue":"13","key":"9663_CR7","doi-asserted-by":"crossref","first-page":"1824","DOI":"10.1016\/j.dam.2006.03.031","volume":"154","author":"P. Burzyn","year":"2006","unstructured":"Burzyn, P., Bonomo, F., Dur\u00e1n, G.: NP-completeness results for edge modification problems. Discrete Appl. Math. 154(13), 1824\u20131844 (2006)","journal-title":"Discrete Appl. Math."},{"key":"9663_CR8","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":"9663_CR9","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). Preliminary version presented at\u00a0COCOON\u00a0\u201902","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"1","key":"9663_CR10","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.jcss.2011.04.001","volume":"78","author":"J. Chen","year":"2012","unstructured":"Chen, J., Meng, J.: A 2k kernel for the cluster editing problem. J. Comput. Syst. Sci. 78(1), 211\u2013220 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"9663_CR11","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1145\/1854776.1854800","volume-title":"Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology (ACM-BCB\u00a0\u201910)","author":"M. Chimani","year":"2010","unstructured":"Chimani, M., Rahmann, S., B\u00f6cker, S.: Exact ILP solutions for phylogenetic minimum flip problems. In: Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology (ACM-BCB\u00a0\u201910), pp. 147\u2013153. ACM, New York (2010)"},{"issue":"3","key":"9663_CR12","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.tcs.2005.10.004","volume":"351","author":"P. Damaschke","year":"2006","unstructured":"Damaschke, P.: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci. 351(3), 337\u2013350 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9663_CR13","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, Berlin (1999)"},{"key":"9663_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1007\/11847250_25","volume-title":"Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC\u00a0\u201906)","author":"M.R. Fellows","year":"2006","unstructured":"Fellows, M.R.: The lost continent of polynomial time: Preprocessing and kernelization. In: Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC\u00a0\u201906). Lecture Notes in Computer Science, vol. 4169, pp. 276\u2013277. Springer, Berlin (2006)"},{"issue":"1","key":"9663_CR15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.disopt.2010.09.006","volume":"8","author":"M.R. Fellows","year":"2011","unstructured":"Fellows, M.R., Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Graph-based data clustering with overlaps. Discrete Optim. 8(1), 2\u201317 (2011)","journal-title":"Discrete Optim."},{"key":"9663_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1007\/978-3-540-74240-1_27","volume-title":"Proceedings of the\u00a016th International Symposium on Fundamentals of Computation Theory (FCT\u00a0\u201916)","author":"M.R. Fellows","year":"2007","unstructured":"Fellows, M.R., Langston, M.A., Rosamond, F.A., Shaw, P.: Efficient parameterized preprocessing for cluster editing. In: Proceedings of the\u00a016th International Symposium on Fundamentals of Computation Theory (FCT\u00a0\u201916). Lecture Notes in Computer Science, vol. 4639, pp. 312\u2013321. Springer, Berlin (2007)"},{"key":"9663_CR17","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"4","key":"9663_CR18","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","volume":"38","author":"J. Gramm","year":"2005","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Graph-modeled data clustering: Exact algorithms for clique generation. Theory Comput. Syst. 38(4), 373\u2013392 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9663_CR19","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":"9663_CR20","doi-asserted-by":"crossref","unstructured":"Guillemot, S., Havet, F., Paul, C., Perez, A.: On the (non-)existence of polynomial kernels for P l -free edge modification problems. Algorithmica (2012, to appear)","DOI":"10.1007\/s00453-012-9619-5"},{"key":"9663_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1007\/978-3-540-77120-3_79","volume-title":"Proceedings of the 18th\u00a0International Symposium on Algorithms and Computation (ISAAC\u00a0\u201907)","author":"J. Guo","year":"2007","unstructured":"Guo, J.: Problem kernels for NP-complete edge deletion problems: split and related graphs. In: Proceedings of the 18th\u00a0International Symposium on Algorithms and Computation (ISAAC\u00a0\u201907). Lecture Notes in Computer Science, vol. 4835, pp. 915\u2013926. Springer, Berlin (2007)"},{"issue":"21\u201323","key":"9663_CR22","first-page":"2045","volume":"410","author":"J. Guo","year":"2009","unstructured":"Guo, J.: A more effective linear kernelization for Cluster Editing. Theor. Comput. Sci. 410(21\u201323), 2045\u20132053 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9663_CR23","doi-asserted-by":"crossref","first-page":"1662","DOI":"10.1137\/090767285","volume":"24","author":"J. Guo","year":"2010","unstructured":"Guo, J., Komusiewicz, C., Niedermeier, R., Uhlmann, J.: A more relaxed model for graph-based data clustering: s-plex cluster editing. SIAM J. Discrete Math. 24(4), 1662\u20131683 (2010)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"9663_CR24","doi-asserted-by":"crossref","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. SIGACT News 38(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"key":"9663_CR25","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, 19\u201328 (1991)","journal-title":"Networks"},{"key":"9663_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1007\/3-540-54945-5_49","volume-title":"Proceedings of the 2nd International Symposium on Algorithms (ISA\u00a0\u201991)","author":"W. Hsu","year":"1991","unstructured":"Hsu, W., Ma, T.: Substitution decomposition on chordal graphs and applications. In: Proceedings of the 2nd International Symposium on Algorithms (ISA\u00a0\u201991). Lecture Notes in Computer Science, vol. 557, pp. 52\u201360. Springer, Berlin (1991)"},{"issue":"1","key":"9663_CR27","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1093\/comjnl\/bxm040","volume":"51","author":"F. H\u00fcffner","year":"2008","unstructured":"H\u00fcffner, F., Niedermeier, R., Wernicke, S.: Techniques for practical fixed-parameter algorithms. Comput. J. 51(1), 7\u201325 (2008)","journal-title":"Comput. J."},{"key":"9663_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1007\/978-3-642-11269-0_22","volume-title":"Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC\u00a0\u201909)","author":"S. Kratsch","year":"2009","unstructured":"Kratsch, S., Wahlstr\u00f6m, M.: Two edge modification problems without polynomial kernels. In: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC\u00a0\u201909). Lecture Notes in Computer Science, vol. 5917, pp. 264\u2013275. Springer, Berlin (2009)"},{"key":"9663_CR29","first-page":"536","volume-title":"Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a0\u201994)","author":"R.M. McConnell","year":"1994","unstructured":"McConnell, R.M., Spinrad, J.: Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a0\u201994), pp. 536\u2013545. ACM\/SIAM, New York (1994)"},{"issue":"1","key":"9663_CR30","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"A. Natanzon","year":"2001","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discrete Appl. Math. 113(1), 109\u2013128 (2001)","journal-title":"Discrete Appl. Math."},{"key":"9663_CR31","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"crossref","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 Lecture Series in Mathematics and Its Applications, vol. 31. Oxford University Press, Oxford (2006)"},{"key":"9663_CR32","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0020-0190(00)00004-1","volume":"73","author":"R. Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parameter-tractable algorithms. Inf. Process. Lett. 73, 125\u2013129 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9663_CR33","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."},{"issue":"1","key":"9663_CR34","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00224-007-9032-7","volume":"44","author":"F. Protti","year":"2009","unstructured":"Protti, F., da Silva, M.D., Szwarcfiter, J.L.: Applying modular decomposition to parameterized cluster editing problems. Theory Comput. Syst. 44(1), 91\u2013104 (2009)","journal-title":"Theory Comput. Syst."},{"key":"9663_CR35","unstructured":"Uhlmann, J.: Multivariate algorithmics in biological data analysis. PhD thesis, Universit\u00e4tsverlag der TU Berlin (2011)"},{"issue":"1","key":"9663_CR36","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebr. Discrete Methods 2(1), 77\u201379 (1981)","journal-title":"SIAM J. Algebr. Discrete Methods"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9663-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9663-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9663-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,30]],"date-time":"2019-06-30T04:12:44Z","timestamp":1561867964000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9663-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,26]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["9663"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9663-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6,26]]}}}