论文部分内容阅读
本文考虑了具有参数三角不等式性质的最长哈密尔顿路问题，并给出了近似算法：(1)对未固定顶点的最长哈密尔顿路问题，分别给出了近似值为4r+1/6r-1/2nr和4/6+l-1/6/r(l为圈覆盖中的圈数）的近似算法，其时间复杂度都为O(n3)；(2)对固定一个顶点的最长哈密尔顿路问题，给出了近似算法，其时间复杂度为O(n4).当y=1时，(2)中的算法就变成了5/6-近似算法，这一结果要好于Monnot[20]的1/2-近似算法。