文献类型：期刊文献

英文题名：Approximation Algorithms fortheCapacitated Min-Max andMinimum Graph Cover Problems

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

机构：[1] School of Mathematics, East China University of Science and Technology, Shanghai, 200237, China

年份：2025

卷号：15434 LNCS

起止页码：18

外文期刊名：Lecture Notes in Computer Science

收录：EI(收录号：20252118454570)

语种：英文

外文关键词：Graph algorithms - Linearization - Trees (mathematics)

摘要：In this paper we obtain improved approximation algorithms for the Capacitated Min-Max Graph Cover Problems and the first constant-factor approximation algorithms for the Capacitated Minimum Graph Cover Problems. These problems are capacitated extension of the well-known min-max and minimum graph cover problems. We introduce several new ideas to bring down the approximation ratios for the Capacitated Min-Max Graph Cover Problems. For the Capacitated Minimum Graph Cover Problems, the constant-factor approximation algorithms are achieved byan approximation-preserving reduction to the corresponding uncapacitated problems. ? The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.