An Improved FPT Algorithm for The Flip Distance Problem
An Improved FPT Algorithm for The Flip Distance Problem
复制标题
翻转距离问题的改进FPT算法
DOI：
10.1016/j.ic.2021.104708
复制
发表时间：
2021
影响因子：
1
通讯作者：
Jianxin Wang
中科院分区：
文献类型：
--
作者：
Qilong Feng;Shaohua Li;Xiangzhong Meng;Jianxin Wang
给定欧氏平面上的一组点P和P的两个三角剖分，这两个三角剖分之间的翻转距离是将一个三角剖分变换为另一个三角剖分所需的最小翻转次数。参数化翻转距离问题是决定两个给定三角剖分之间的翻转距离是否等于给定的整数k。以前最好的FPT算法运行时间为O <$（k <$ck）（c≤ 2× 14 11），其中每个步骤有14个可能的选择，动作序列的长度以11 k为界。通过分析翻转序列的基本性质，我们算法的每一步只有五种可能的选择。基于一个辅助图G，我们证明了我们算法的动作序列的长度有界于2| G|.因此，我们提出了一个时间复杂度为O <$（k <$32 k）的FPT算法.
Given a set P of points in the Euclidean plane and two triangulations of P, the flip distance between these two triangulations is the minimum number of flips required to transform one triangulation into the other. The Parameterized Flip Distance problem is to decide if the flip distance between two given triangulations is equal to a given integer k. The previous best FPT algorithm runs in time O⁎(k⋅ c k)(c≤ 2× 14 11), where each step has fourteen possible choices, and the length of the action sequence is bounded by 11k. By analyzing the underlying properties of the flip sequence, each step of our algorithm has only five possible choices. Based on an auxiliary graph G, we prove that the length of the action sequence for our algorithm is bounded by 2| G|. As a result, we present an FPT algorithm running in time O⁎(k⋅ 32 k).