文献类型：期刊文献

英文题名：Approximating Graphic Min-Max and Minimum Cycle/Path/Tree Cover Problems

作者：Yu, Wei[1];Liu, Zhaohui[1]

机构：[1]East China Univ Sci & Technol, Sch Math, Shanghai 200237, Peoples R China

年份：2025

卷号：372

起止页码：314

外文期刊名：DISCRETE APPLIED MATHEMATICS

收录：;EI(收录号：20252018414306);WOS:【SCI-EXPANDED(收录号:WOS:001492908300001)】；

基金：We are very grateful to the anonymous reviewers for their valuable suggestions and insightful comments which greatly improve the presentation of this paper. This research is supported by the National Natural Science Foundation of China (No. 12371317) and the Natural Science Foundation of Shanghai, China (No. 24ZR1416900) .

语种：英文

外文关键词：Approximation algorithm; Graphic TSP; Cycle Cover; Path Cover; Tree Cover

摘要：In this work we consider the Graphic Min-Max Cycle/Path/Tree Cover Problem and the Graphic Minimum Cycle/Path/Tree Cover Problem, some of which generalize the famous Graphic TSP. For all six problems, we obtain approximation algorithms with better ratios than the corresponding problems defined on general metrics. For the Graphic Minimum Path Cover Problem, we even show a best possible approximation ratio of 2, assuming P not equal NP. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.