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

摘要：

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

关键词：Hamilton路、NP完全、Halin图、扇

所属期刊栏目：34

分类号：TP3(计算技术、计算机技术)

资助基金：广东省科技攻关计划A10103

在线出版日期：2007-11-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：176-180,217