标题:A New Algebraic Approach to Finding all Simple Paths and Cycles in Undirected Graphs
作者:Yang, Runtao; Gao, Rui; Zhang, Chengjin
通讯作者:Yang, RT
作者机构:[Yang, Runtao; Gao, Rui; Zhang, Chengjin] Shandong Univ, Sch Control Sci & Engn, Jinan, Peoples R China.; [Zhang, Chengjin] Shandong Univ Weihai, Sc 更多
会议名称:IEEE International Conference on Information and Automation 2015
会议日期:AUG 08-10, 2015
来源:2015 IEEE INTERNATIONAL CONFERENCE ON INFORMATION AND AUTOMATION
出版年:2015
页码:1887-1892
关键词:simple paths and cycles; semi-tensor product; algebraic approach;; pathfinding
摘要:Finding all simple paths and cycles in undirected graphs is a generic problem that covers a wide range of research areas. The problem has been discussed only to a minor extent in recent years. This paper investigates the problem and provides a necessary and sufficient condition for simple paths and cycles. With the theory of the semi-tensor product, a necessary condition for simple paths and cycles is then proposed to reduce the search space. Based on the above-mentioned results, a new algebraic algorithm to find all simple paths and cycles in undirected graphs is presented. The algorithm involves only algebraic operations, reduces the search space, and decreases the computational complexity. An illustrative example is finally given to demonstrate the effectiveness of the presented algorithm.
收录类别:CPCI-S
WOS核心被引频次:2
资源类型:会议论文
TOP