用分层关联方法求有向图中所有Hamilton回路的算法

• 作者: 姜云飞 文中华
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 有向图 Hamilton回路 关联关系 初级通路
• 年，卷（期）: 2005,（10）
• 所属期刊栏目: 算法理论
• 页码范围: 1809-1814
• 页数: 6页
• 分类号: TP301.6
• 字数: 6429字
• 语种: 中文

摘要

首先建立了有向图中初级通路的关联关系,并对初级通路的关联关系进行了分析,得到了关于初级通路关联关系的一些重要结果.然后,对初级通路的关联关系进行了分级分层.在此基础上,设计了求有向图中所有Hamilton回路的算法.该算法利用长度为k的初级通路及其分层关联关系逐步求长度为k+1的初级通路及其分层关联关系的方法,求得有向图的所有Hamilton回路.通过理论分析可以看到,所设计的算法与已有的求有向图的所有Hamilton回路的算法相比,避免了大量的重复计算,从而降低了算法复杂度,为求解Hamilton回路问题提供了新思路.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	文中华	中山大学软件研究所	37	143	7.0	10.0
3	姜云飞	中山大学软件研究所	84	1013	18.0	28.0