标题:An approximation algorithm for the shortest cycle in an undirected unweighted graph
作者:Lv, Xu-Guang ;Zhu, Da-Ming
通讯作者:Lv, XG
作者机构:[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
出版年:2010
卷:1
页码:297-300
DOI:10.1109/CMCE.2010.5610495
关键词: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.
收录类别:EI;SCOPUS
Scopus被引频次:1
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-78650012999&doi=10.1109%2fCMCE.2010.5610495&partnerID=40&md5=cf53a287b03db7b8af3f9b11d46b9606
TOP