{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T18:03:13Z","timestamp":1775671393134,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,11,5]],"date-time":"2023-11-05T00:00:00Z","timestamp":1699142400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,11,5]],"date-time":"2023-11-05T00:00:00Z","timestamp":1699142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,4]]},"DOI":"10.1007\/s00454-023-00596-9","type":"journal-article","created":{"date-parts":[[2023,11,5]],"date-time":"2023-11-05T22:01:32Z","timestamp":1699221692000},"page":"702-718","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An $$\\mathcal {O}(3.82^{k})$$ Time $$\\textsf {FPT}$$ Algorithm for Convex Flip Distance"],"prefix":"10.1007","volume":"73","author":[{"given":"Haohong","family":"Li","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7315-4471","authenticated-orcid":false,"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,11,5]]},"reference":[{"issue":"2","key":"596_CR1","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.comgeo.2004.02.003","volume":"29","author":"O Aichholzer","year":"2004","unstructured":"Aichholzer, O., Hurtado, F., Noy, M.: A lower bound on the number of triangulations of planar point sets. Comput. Geom. Theory Appl. 29(2), 135\u2013145 (2004)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"596_CR2","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/s00454-015-9709-7","volume":"54","author":"O Aichholzer","year":"2015","unstructured":"Aichholzer, O., Mulzer, W., Pilz, A.: Flip distance between triangulations of a simple polygon is NP-complete. Discrete Comput. Geom. 54(2), 368\u2013389 (2015)","journal-title":"Discrete Comput. Geom."},{"issue":"6","key":"596_CR3","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1016\/0167-8655(92)90047-4","volume":"13","author":"A Bonnin","year":"1992","unstructured":"Bonnin, A., Pallo, J.-M.: A shortest path metric on unlabeled binary trees. Pattern Recognit. Lett. 13(6), 411\u2013415 (1992)","journal-title":"Pattern Recognit. Lett."},{"key":"596_CR4","doi-asserted-by":"crossref","unstructured":"Bosch-Calvo, M., Kelk, S.: An improved kernel for the flip distance problem on simple convex polygons. Inf. Process. Lett. 182, #\u00a0106381 (2023)","DOI":"10.1016\/j.ipl.2023.106381"},{"issue":"1","key":"596_CR5","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.comgeo.2008.04.001","volume":"42","author":"P Bose","year":"2009","unstructured":"Bose, P., Hurtado, F.: Flips in planar graphs. Comput. Geom. Theory Appl. 42(1), 60\u201380 (2009)","journal-title":"Comput. Geom. Theory Appl."},{"key":"596_CR6","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1080\/00207160500069870","volume":"82","author":"Y-J Chen","year":"2005","unstructured":"Chen, Y.-J., Chang, J.-M., Wang, Y.-L.: An efficient algorithm for estimating rotation distance between two binary trees. Int. J. Comput. Math. 82, 1095\u20131106 (2005)","journal-title":"Int. J. Comput. Math."},{"issue":"16","key":"596_CR7","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1016\/j.ipl.2009.04.023","volume":"109","author":"S Cleary","year":"2009","unstructured":"Cleary, S., John, K.S.: Rotation distance is fixed-parameter tractable. Inf. Process. Lett. 109(16), 918\u2013922 (2009)","journal-title":"Inf. Process. Lett."},{"key":"596_CR8","doi-asserted-by":"publisher","first-page":"385","DOI":"10.7155\/jgaa.00212","volume":"14","author":"S Cleary","year":"2010","unstructured":"Cleary, S., John, K.S.: A linear-time approximation algorithm for rotation distance. J. Graph Algorithms Appl. 14, 385\u2013390 (2010)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"596_CR9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0020-0190(82)90083-7","volume":"15","author":"K Culik","year":"1982","unstructured":"Culik, K., Wood, D.: A note on some tree similarity measures. Inf. Process. Lett. 15(1), 39\u201342 (1982)","journal-title":"Inf. Process. Lett."},{"key":"596_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, New York (1999)"},{"key":"596_CR11","doi-asserted-by":"crossref","unstructured":"Feng, Q., Li, S., Meng, X., Wang, J.: An improved FPT algorithm for the flip distance problem. Inf. Comput. 281, #\u00a0104708 (2021)","DOI":"10.1016\/j.ic.2021.104708"},{"key":"596_CR12","doi-asserted-by":"crossref","unstructured":"Fordham, S., Cleary, S.: Minimal length elements of Thompson\u2019s groups $$F(p)$$. Geom. Dedicata 141, 163\u2013180 (2007)","DOI":"10.1007\/s10711-008-9350-1"},{"issue":"8","key":"596_CR13","first-page":"570","volume":"2","author":"S Hanke","year":"1996","unstructured":"Hanke, S., Ottmann, T., Schuierer, S.: The edge-flipping distance of triangulations. J. Univers. Comput. Sci. 2(8), 570\u2013579 (1996)","journal-title":"J. Univers. Comput. Sci."},{"issue":"3","key":"596_CR14","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/PL00009464","volume":"22","author":"F Hurtado","year":"1999","unstructured":"Hurtado, F., Noy, M., Urrutia, J.: Flipping edges in triangulations. Discrete Comput. Geom. 22(3), 333\u2013346 (1999)","journal-title":"Discrete Comput. Geom."},{"issue":"11","key":"596_CR15","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/368996.369025","volume":"5","author":"AB Kahn","year":"1962","unstructured":"Kahn, A.B.: Topological sorting of large networks. Commun. ACM 5(11), 558\u2013562 (1962)","journal-title":"Commun. ACM"},{"issue":"2","key":"596_CR16","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/s00454-017-9867-x","volume":"58","author":"I Kanj","year":"2017","unstructured":"Kanj, I., Sedgwick, E., Xia, G.: Computing the flip distance between triangulations. Discrete Comput. Geom. 58(2), 313\u2013344 (2017)","journal-title":"Discrete Comput. Geom."},{"key":"596_CR17","unstructured":"Kanj, I., Xia, G.: Flip distance is in FPT time $${O}(n+ k \\cdot c^k)$$. In: 32nd International Symposium on Theoretical Aspects of Computer Science (Garching 2015). Leibniz Int. Proc. Inform., vol 30, pp. 500\u2013512. Leibniz-Zent., Wadern (2015)"},{"issue":"4","key":"596_CR18","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0012-365X(72)90093-3","volume":"3","author":"C Lawson","year":"1972","unstructured":"Lawson, C.: Transforming triangulations. Discrete Math. 3(4), 365\u2013372 (1972)","journal-title":"Discrete Math."},{"key":"596_CR19","doi-asserted-by":"crossref","unstructured":"Li, M., Zhang, L.: Better approximation of diagonal-flip transformation and rotation transformation. In: 4th Annual International Conference on Computing and Combinatorics (Taipei 1998). Lecture Notes in Computer Science, vol. 1449, pp. 85\u201394. Springer, Berlin (1998)","DOI":"10.1007\/3-540-68535-9_12"},{"key":"596_CR20","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.comgeo.2014.11.001","volume":"49","author":"A Lubiw","year":"2015","unstructured":"Lubiw, A., Pathak, V.: Flip distance between two triangulations of a point set is NP-complete. Comput. Geom. Theory Appl. 49, 17\u201323 (2015)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"12","key":"596_CR21","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1016\/j.ipl.2010.04.022","volume":"110","author":"J Lucas","year":"2010","unstructured":"Lucas, J.: An improved kernel size for rotation distance in binary trees. Inf. Process. Lett. 110(12), 481\u2013484 (2010)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"596_CR22","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0020-0190(89)90069-0","volume":"31","author":"F Luccio","year":"1989","unstructured":"Luccio, F., Pagli, L.: On the upper bound on the rotation distance of binary trees. Inf. Process. Lett. 31(2), 57\u201360 (1989)","journal-title":"Inf. Process. Lett."},{"key":"596_CR23","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, New York (2006)"},{"issue":"6","key":"596_CR24","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/0020-0190(87)90214-6","volume":"25","author":"J Pallo","year":"1987","unstructured":"Pallo, J.: On the rotation distance in the lattice of binary trees. Inf. Process. Lett. 25(6), 369\u2013373 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"596_CR25","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1016\/j.comgeo.2014.01.001","volume":"47","author":"A Pilz","year":"2014","unstructured":"Pilz, A.: Flip distance between triangulations of a planar point set is APX-hard. Comput. Geom. Theory Appl. 47(5), 589\u2013604 (2014)","journal-title":"Comput. Geom. Theory Appl."},{"key":"596_CR26","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.aim.2014.02.035","volume":"259","author":"L Pournin","year":"2014","unstructured":"Pournin, L.: The diameter of associahedra. Adv. Math. 259, 13\u201342 (2014)","journal-title":"Adv. Math."},{"key":"596_CR27","doi-asserted-by":"crossref","unstructured":"Sleator, D., Tarjan, R., Thurston, W.: Rotation distance, triangulations, and hyperbolic geometry. J. Am. Math. Soc. 1, 647\u2013681 (1988)","DOI":"10.1090\/S0894-0347-1988-0928904-4"},{"key":"596_CR28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609589","volume-title":"Enumerative Combinatorics","author":"RP Stanley","year":"1999","unstructured":"Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00596-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00596-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00596-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,17]],"date-time":"2025-03-17T14:57:58Z","timestamp":1742223478000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00596-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,5]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["596"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00596-9","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,5]]},"assertion":[{"value":"17 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The algorithm presented in this paper has been implemented in C++ and is available in the GitHub Repository, .","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Algorithm"}}]}}