An O(3.82ᵏ) time FPT algorithm for convex flip distance

DOI10.1007/S00454-023-00596-9MaRDI QIDQ7009907zbMATH OpenFDO

Authors Haohong Li, Ge Xia

Publication date 19 March 2025

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00454-023-00596-9

zbMATH Keywords

exact algorithmsflip distanceparameterized complexityrotation distancetriangulations

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A linear-time approximation algorithm for rotation distance
• A lower bound on the number of triangulations of planar point sets
• A note on some tree similarity measures
• An efficient algorithm for estimating rotation distance between two binary trees
• An improved FPT algorithm for the flip distance problem
• An improved kernel for the flip distance problem on simple convex polygons
• An improved kernel size for rotation distance in binary trees
• Computing the flip distance between triangulations
• Flip distance between triangulations of a planar point set is APX-hard
• Flip distance between triangulations of a simple polygon is NP-complete
• Flip distance between two triangulations of a point set is NP-complete
• Flip distance is in FPT time O(n+ k c^k)
• Flipping edges in triangulations
• Flips in planar graphs
• scientific article; zbMATH DE number 1222822 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1418487 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Minimal length elements of Thompson's groups F(p).
• On the upper bound on the rotation distance of binary trees
• Rotation distance is fixed-parameter tractable
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• The diameter of associahedra
• Topological sorting of large networks
• Transforming triangulations

Cited in

(1)

• Hardness of finding combinatorial shortest paths on graph associahedra

This page was built for publication: An \(\mathcal{O}(3.82^k)\) time \(\mathsf{FPT}\) algorithm for convex flip distance

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