2-Club簇图顶点删除问题改进参数算法

摘要

2-club簇图修改问题是经典的NP难问题.对通过对2-club簇图修改问题的参数算法进行研究,提出简化问题实例的若干规则.基于对2-club簇图结构的分析和提出的简化规则,并采用自顶向下的分支方法,提出时间复杂度为O*(3.24k)的固定参数算法,降低了目前求解该问题的时间复杂度.%2-club cluster graph modification problems are classical NP-hard problems. The parameterized algorithms were studied for the 2-club cluster graph modification problems, and several reduction rules were presented to reduce the size of input instance. Based on the structure analysis of the 2-club cluster graph and the reduction rules presented, by applying a top-down approach, a fixed-parameterized algorithm with running time O*(3.24k) was presented, which improves the current algorithm solving the 2-club cluster graph modification problems.