CAJ | 학술논문

最小顶点覆盖问题是组合优化中经典NP-Hard问题之一，其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术，该技术主要用于对分支降阶的递归算法进行复杂性分析，其核心思想可以理解为依据问题不同的特征设置一组相应的权值，以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题，并通过加权分治技术分析得出该算法的时间复杂度为O（1．255n），优于常规分析下的时间复杂度O（1．325n）。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。
최소정점복개문제시조합우화중경전NP-Hard문제지일，기재실제문제중유착엄범적응용。가권분치기술시산법설계화복잡성분석중적신기술，해기술주요용우대분지강계적체귀산법진행복잡성분석，기핵심사상가이리해위의거문제불동적특정설치일조상응적권치，이구강저해산법최배정황하적시간복잡도。본문의거가권분치기술설계출일개분지강계체귀산법래구해최소정점복개문제，병통과가권분치기술분석득출해산법적시간복잡도위O（1．255n），우우상규분석하적시간복잡도O（1．325n）。본문중적결과표명운용상술방법강저산법적시간복잡도시비상유효적。
Minimum vertex cover set problem is a well-known NP-Hard problem in the area of combinatorial opti-mization and has important applications in many fields.The analytical technology of Measure and Conquer is widely used to analyze the worst-case running time of exact algorithms based on branch and reduce.The main idea of Measure and Conquer is focused on choosing a refined non-standard measure to measure the size of the problem and its sub-problems at the each branching phase.In this work, we first use the technology of Branch and Reduce to design an exact algorithm for the minimum vertex cover problem, then use two kinds of methods to analyze the worst-case time complexity of the algorithm.We improve the worst-case time complexity of the same algorithm from O(1.325n) to O(1.255n) by employing the method of Measure and Conquer.The results of this work indicate that Measure and Conquer approach can significantly speed up exact algorithms and has wide appli-cations in the analysis of exact algorithms.