Approximation algorithms for the prize-collecting rural postman problem

Hong Li, Jianping Li, Wei Li +2

In this paper, we study the prize-collecting rural postman problem (PCRPP), a variant of the rural postman problem. In an instance of the PCRPP, one is given an undirected graph wh…