标题：An approximation algorithm for the shortest cycle in an undirected unweighted graph
作者：Lv, Xu-Guang ;Zhu, Da-Ming
作者机构：[Lv, Xu-Guang ;Zhu, Da-Ming ] Department of Computer Science and Technology, Shandong University, Jinan, China
会议名称：2010 International Conference on Computer, Mechatronics, Control and Electronic Engineering, CMCE 2010
会议日期：24 August 2010 through 26 August 2010
来源：2010 International Conference on Computer, Mechatronics, Control and Electronic Engineering, CMCE 2010
关键词：Bridges; Shortest cycle; Sparse; Undirected unweighted graph
摘要：This paper improves Itai and Rodeh's 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. © 2010 IEEE.