摘要： 在赋权图中，求任意给定两点之间的最优（边权值之和最小）Hamilton路问题，简称OHP问题，是计算机领域的一个经典算法问题，它在网络路由选择和计算机的许多领域都有广泛应用。该问题是NP完全的。Halln图是对树和环网络的非平凡概括，因此求赋权Halin图的OHP问题是非常有意义的。但当前仍没找到该问题的有效算法。本文通过递归压缩Halin图中的扇，设计了一个求解赋权Halin图OHP的有效算法，并给出算法的正确性证明和复杂度分析。
温雪莲 娄定俊 陆芸婷 梁华金. 求Halin图中给定两点之间最优Hamilton路的有效算法[J]. 计算机科学, 2007, 34(9): 176-180. https://doi.org/
WEN Xue-Lian, LOU Ding-Jun, LU Yun-Ting, LIANG Hua-Jin （Department of Gomputer Science, Sun Yat-sen University, Guangzhou 510275）. [J]. Computer Science, 2007, 34(9): 176-180. https://doi.org/
首页