改进的最小顶点覆盖问题的贪婪算法 (2012年)

【文件属性】：

文件名称：改进的最小顶点覆盖问题的贪婪算法 (2012年)

文件大小：694KB

文件格式：PDF

更新时间：2024-07-02 10:56:20

自然科学 论文

通过分析竞争决策算法、混合贪婪算法和快速降阶算法,在顶点的度及贪心算法的基础上,对顶点添加访问标记符号,并在减治法的概念下设计了最小顶点覆盖问题的一种较为中和性的贪婪算法。该算法消除了邻接度数的概念,直接运用顶点度数来完成算法的实现,从而降低了算法的时间复杂度,且更易于编程。该算法在最坏情况下的时间复杂度为O(|V|2)。