文献类型：期刊文献

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

英文题名：Exact Algorithms for Some Variants of the Min-Max k-Traveling Salesmen Problem on a Tree

作者：高哲成[1];余炜[1];刘朝晖[1]

机构：[1]华东理工大学数学学院,上海200237

年份：2021

卷号：47

期号：6

起止页码：769

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：Scopus;北大核心:【北大核心2020】；CSCD:【CSCD_E2021_2022】；

基金：国家自然科学基金(11671135);上海市自然科学基金(19ZR1411800);中央高校基本科研业务费(22220184028)。

语种：中文

中文关键词：拟多项式;最小-最大;旅行商问题;路覆盖;中国邮递员问题

外文关键词：pseudo-polynomial;min-max;traveling salesman problem;path cover;Chinese postmen problem

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