Flip distance is in FPT time O(n+ k c^k)

DOI10.4230/LIPICS.STACS.2015.500MaRDI QIDQ2955019zbMATH OpenOpenAlexFDO

Authors Ge Xia, Iyad Kanj

Publication date 24 January 2017

Full work available at URL https://dx.doi.org/10.4230/LIPIcs.STACS.2015.500

zbMATH Keywords

triangulationsparameterized algorithmsflip distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Computing the flip distance between triangulations
• An improved FPT algorithm for the flip distance problem
• scientific article; zbMATH DE number 7204399
• Flip distance between two triangulations of a point set is NP-complete

Cited in

(11)

• On the parameterized complexity of reconfiguration of connected dominating sets
• Flip paths between lattice triangulations
• Introduction to reconfiguration
• scientific article; zbMATH DE number 7204399 (Why is no real title available?)
• An \(\mathcal{O}(3.82^k)\) time \(\mathcal{FPT}\) algorithm for convex flip distance
• An improved kernel for the flip distance problem on simple convex polygons
• Flip distance to some plane configurations
• An improved FPT algorithm for the flip distance problem
• Flip distance to some plane configurations
• scientific article; zbMATH DE number 7764115 (Why is no real title available?)
• Computing the flip distance between triangulations

This page was built for publication: Flip distance is in FPT time \(O(n+ k \cdot c^k)\)

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