随机图的哈密尔顿回路实验研究

• 作者: 刘蕻 梅俊杰 王以松 许欢
• 来源期刊: 贵州大学学报（自然科学版）
• 学科: 工学
• 关键词: 哈密尔顿回路 随机图 回答集程序设计
• 年，卷（期）: 2013,（3）
• 所属期刊栏目: 计算机技术
• 页码范围: 77-81
• 页数: 5页
• 分类号: TP399
• 字数: 3073字
• 语种: 中文

摘要

哈密尔顿回路问题是图论的经典NP-难解问题之一,在计算机科学中被广泛用作测试用例以测试算法/系统的有效性,包括可满足性(SAT)、回答集程序设计(ASP)以及约束可满足问题(CSP)等.在本文中,我们通过ASP实验研究了40到100个节点(步长为10)随机图的哈密尔顿回路存在性、不存在性、以及难于计算等的分布情况,结果表明它们都具有一定的规律.这不仅对随机图的哈密尔顿回路本身是有益的探索,也为生成随机图哈密尔顿测试用例提供了有益的指导.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王以松	贵州大学计算机科学与信息学院	23	51	4.0	5.0
2	梅俊杰	贵州大学计算机科学与信息学院	4	6	1.0	2.0
3	刘蕻	贵州大学计算机科学与信息学院	4	6	1.0	2.0
4	许欢	贵州大学计算机科学与信息学院	3	8	2.0	2.0