高级检索

    高哲成, 余炜, 刘朝晖. 树上的最小-最大k旅行商问题若干变种的精确算法[J]. 华东理工大学学报(自然科学版), 2021, 47(6): 769-778. DOI: 10.14135/j.cnki.1006-3080.20200317001
    引用本文: 高哲成, 余炜, 刘朝晖. 树上的最小-最大k旅行商问题若干变种的精确算法[J]. 华东理工大学学报(自然科学版), 2021, 47(6): 769-778. DOI: 10.14135/j.cnki.1006-3080.20200317001
    GAO Zhecheng, YU Wei, LIU Zhaohui. Exact Algorithms for Some Variants of the Min-Max k-Traveling Salesmen Problem on a Tree[J]. Journal of East China University of Science and Technology, 2021, 47(6): 769-778. DOI: 10.14135/j.cnki.1006-3080.20200317001
    Citation: GAO Zhecheng, YU Wei, LIU Zhaohui. Exact Algorithms for Some Variants of the Min-Max k-Traveling Salesmen Problem on a Tree[J]. Journal of East China University of Science and Technology, 2021, 47(6): 769-778. DOI: 10.14135/j.cnki.1006-3080.20200317001

    树上的最小-最大k旅行商问题若干变种的精确算法

    Exact Algorithms for Some Variants of the Min-Max k-Traveling Salesmen Problem on a Tree

    • 摘要: 树上的最小-最大 k 旅行商问题是多旅行商问题在树形结构中的推广问题。研究了树上的最小-最大 k 旅行商问题、树上的多仓库最小-最大 k 旅行商问题以及树上的最小-最大 k 路覆盖问题,提出了基于自下而上的动态规划的拟多项式时间精确算法。将树上的多仓库最小-最大 k 旅行商问题的算法推广到树上的多仓库最小-最大 k 路覆盖问题和树上的多仓库最小-最大 k 中国邮递员问题,分别给出了首个拟多项式时间精确算法。

       

      Abstract: The min-max k -traveling salesmen problem on a tree (Min-Max k-TSPT) is an extension of multiple traveling salesmen problem in tree structure. In this paper, Min-Max k-TSPT, multi-depot Min-Max k-TSPT and min-max k -path cover problem on a tree (Min-Max k-PCPT) were studied. We present pseudo-polynomial exact algorithms for them by bottom-up dynamic programming. Besides, based on the algorithm of multi-depot Min-Max k-TSPT, we devise pseudo-polynomial exact algorithms solving multi-depot Min-Max k-PCPT and multi-depot min-max k -Chinese postmen problem on a tree (multi-depot Min-Max k-CPPT) for the first time.

       

    /

    返回文章
    返回