文献类型：期刊文献

英文题名：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, Shanghai, 200237, China

年份：2019

卷号：11949 LNCS

起止页码：375

外文期刊名：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

收录：EI(收录号：20200508108204)

语种：英文

外文关键词：Undirected graphs - Approximation algorithms

摘要：In this work we study 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 by a minimum size set of closed walks of bounded length. The MCPCP is a special case of the MRPCP with. We give the first approximation algorithms for these two problems with approximation ratios 5 and 4, respectively. ? 2019, Springer Nature Switzerland AG.