删除顶点生成二分图问题的精确算法

分支降阶是目前广泛用于设计精确算法求解NP-Hard问题的技术之一,该技术主要通过快速降阶、分支及递归求解原问题及其子问题.为了降低分支降阶算法的时间复杂度,一方面可以增加降阶规则、改变算法的设计思想;另一方面可以运用更精确的时间复杂度分析方法分析算法.本文针对删除最少顶点生成二分图问题,首先运用常规枚举方法得到一个时间复杂度为O(3n)的算法;然后通过增加降阶规则、改善算法设计和运用加权分治技术分析算法等方法,最终得到一个时间复杂度为O(1.8157n)的精确算法.本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的.