文献类型：期刊文献

英文题名：Approximation algorithms for some Minimum Postmen Cover Problems

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

机构：[1] Department of Mathematics, East China University of Science and Technology, 130 Meilong Road, Shanghai, 200237, China

年份：2022

卷号：319

起止页码：382

外文期刊名：Discrete Applied Mathematics

收录：EI(收录号：20220611611068)

语种：英文

外文关键词：Approximation algorithms - Undirected graphs

摘要：In this work we introduce the Minimum Rural Postmen Cover Problem (MRPCP) and the Minimum Chinese Postmen Cover Problem (MCPCP). The MRPCP aims to cover a given subset R of edges of an undirected weighted graph G=(V,E) by a minimum size set of closed walks of bounded length λ. The MCPCP is a special case of the MRPCP with R=E. We give the first approximation algorithms for these two problems, which have constant approximation ratios of 5 and 4, respectively. ? 2022 Elsevier B.V.