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

DOI10.1016/j.ipl.2023.106381MaRDI QIDQ6161439

Steven Kelk, Miguel Bosch-Calvo

Publication date: 5 June 2023

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

zbMATH Keywords

algorithmstriangulationkernelparameterized complexitysimple convex polygons

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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