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

DOI10.4230/LIPICS.STACS.2015.500zbMATH Open1355.68280OpenAlexW2264222783MaRDI QIDQ2955019FDOQ2955019

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

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

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)

Cited In (11)

• On the parameterized complexity of reconfiguration of connected dominating sets
• Flip paths between lattice triangulations
• Introduction to reconfiguration
• Title not available (Why is that?)
• 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
• Flip distance to some plane configurations
• An improved FPT algorithm for the flip distance problem
• Title not available (Why is that?)
• 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)