摘要
通过分析竞争决策算法、混合贪婪算法和快速降阶算法,在顶点的度及贪心算法的基础上,对顶点添加访问标记符号,并在减治法的概念下设计了最小顶点覆盖问题的一种较为中和性的贪婪算法.该算法消除了邻接度数的概念,直接运用顶点度数来完成算法的实现,从而降低了算法的时间复杂度,且更易于编程.该算法在最坏情况下的时间复杂度为O(|V|2).
Through analyzing the competitive decision algorithm,mixed greedy algorithm and fast reduction algorithm,and based on the concepts of the vertex degree and the idea of the greedy algorithm,the access flag is added to the vertex.Based on these ideas and the concept of decrease and conquer,it is proposed that a relatively neutral greedy algorithm of the minimum vertex cover problem.This algorithm eliminates the concept of adjacency degree,directly using the vertex degree to realize the algorithm,which reduces the time complexity of the algorithm,and easy to programming.In the worst case,the time complexity of the algorithm is O（｜V｜2）.
出处
《内蒙古师范大学学报（自然科学汉文版）》
CAS
北大核心
2012年第2期206-210,共5页
Journal of Inner Mongolia Normal University(Natural Science Edition)
基金
内蒙古师范大学研究生科研创新基金项目(CXJJS11068)
关键词
最小顶点覆盖问题
贪婪算法
顶点的度
访问标记
减治法
minimum vertex cover
greedy algorithm
Vertex Degree
access flag
decrease andconquer
