A Heuristic Approach to Fast NOVCA (Near Optimal Vertex Cover Algorithm) |
| |
作者姓名: | Sanj aya Gajurel Roger Bielefeld |
| |
作者单位: | ITS, Advanced Research Computing, CWR U, Cleveland 44106, USA |
| |
摘 要: | This paper describes an extremely fast polynomial time algorithm, the NOVCA (Near Optimal Vertex Cover Algorithm) that produces an optimal or near optimal vertex cover for any known undirected graph G (V, E). NOVCA is based on the idea of(l) including the vertex having maximum degree in the vertex cover and (2) rendering the degree of a vertex to zero by including all its adjacent vertices. The three versions of algorithm, NOVCA-I, NOVCA-II, and NOVCA-random, have been developed. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any available vertex cover algorithms.
|
关 键 词: | 顶点覆盖 覆盖算法 启发式方法 多项式时间 多项式算法 调整算法 无向图 复杂度 |
本文献已被 维普 等数据库收录! |
|