Back to Search
Start Over
Approximation algorithms for some Minimum Postmen Cover Problems.
- Source :
-
Discrete Applied Mathematics . Oct2022, Vol. 319, p382-393. 12p. - Publication Year :
- 2022
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 319
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 158184672
- Full Text :
- https://doi.org/10.1016/j.dam.2022.01.005