论文研究一种增量式约简方法求解最小顶点覆盖问题.pdf

最小顶点覆盖问题是一个应用很广泛的NP难题，针对该问题给出一种增量式属性约简方法。首先将最小顶点覆盖问题转换为一个决策表的最小属性约简问题；利用增量式属性约简思想，随着图中边数的增多，提出一种更新最小顶点覆盖的增量式属性约简算法；该算法时间复杂度低于计算整个图的最小顶点覆盖的时间复杂度，同时针对大规模图问题，可随着边的增加动态更新最小顶点覆盖，因此降低了属性约简的方法求解最小顶点覆盖问题的运行时间。实验结果表明了该算法的可行性和有效性。