An Approximation Algorithm for the Shortest Cycle in an Undirected Unweighted Graph
This paper improves Itai and Rodehs algorithm for finding a shortest cycle in an undirected unweighted graph.Given an undirected unweighted graph G with n vertices,the algorithm can determine a cycle whose length is at most k+1 where k is the length of the shortest cycle in G.The results of the experiment show that the improved algorithm runs faster than the original one when the input graph meets some special features.
undirected unweighted graph shortest cycle sparse bridges
Lv Xu-guang Zhu Da-ming
Department of Computer Science and Technology Shandong University Jinan, China
国际会议
长春
英文
297-300
2010-08-24（万方平台首次上网日期，不代表论文的发表时间）