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