求Halin图中给定两点之间最优Hamilton路的有效算法

• 作者: 娄定俊 梁华金 温雪莲 陆芸婷
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: Hamilton路 NP完全 Halin图 扇
• 年，卷（期）: 2007,（9）
• 所属期刊栏目: 人工智能及图像处理技术
• 页码范围: 176-180,217
• 页数: 6页
• 分类号: TP3
• 字数: 10076字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2007.09.047

摘要

在赋权图中,求任意给定两点之间的最优(边权值之和最小)Hamilton路问题,简称OHP问题,是计算机领域的一个经典算法问题,它在网络路由选择和计算机的许多领域都有广泛应用.该问题是NP完全的.Halin图是对树和环网络的非平凡概括,因此求赋权Halin图的OHP问题是非常有意义的.但当前仍没找到该问题的有效算法.本文通过递归压缩Halin图中的扇,设计了一个求解赋权Halin图OHP的有效算法,并给出算法的正确性证明和复杂度分析.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	梁华金	中山大学计算机科学系	9	66	4.0	8.0
2	娄定俊	中山大学计算机科学系	5	15	3.0	3.0
3	温雪莲	中山大学计算机科学系	2	8	2.0	2.0
4	陆芸婷	中山大学计算机科学系	6	15	3.0	3.0