An improved kernel for the flip distance problem on simple convex polygons

DOI10.1016/J.IPL.2023.106381MaRDI QIDQ6161439zbMATH OpenFDO

Authors Miguel Bosch-Calvo, Steven Kelk

Publication date 5 June 2023

Published in Information Processing Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/J.IPL.2023.106381

zbMATH Keywords

algorithmskernelparameterized complexitysimple convex polygonstriangulation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• An \(\mathcal{O}(3.82^k)\) time \(\mathcal{FPT}\) algorithm for convex flip distance
• Flip distance is in FPT time O(n+ k c^k)
• Computing the flip distance between triangulations
• An improved kernel size for rotation distance in binary trees

Cites work

• A note on some tree similarity measures
• An efficient upper bound of the rotation distance of binary trees
• An improved FPT algorithm for the flip distance problem
• An improved kernel size for rotation distance in binary trees
• Computing the flip distance between triangulations
• Graph of triangulations of a convex polygon and tree of triangulations
• Kernelization. Theory of parameterized preprocessing
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Rotation distance is fixed-parameter tractable
• Rotation Distance, Triangulations, and Hyperbolic Geometry

Cited in

(4)

• scientific article; zbMATH DE number 7204399 (Why is no real title available?)
• An \(\mathcal{O}(3.82^k)\) time \(\mathsf{FPT}\) algorithm for convex flip distance
• Constrained flips in plane spanning trees
• Flip distance between two triangulations of a point set is NP-complete

This page was built for publication: An improved kernel for the flip distance problem on simple convex polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161439)