Chapter 2: The Complexity of Arc Routing Problems
René van Bevern, Rolf Niedermeier, Manuel Sorge, Mathias Weller · Society for Industrial and Applied Mathematics eBooks · 2015
2.1 ▪ Introduction This chapter is devoted to surveying aspects of computational complexity for three central arc routing problems (and their corresponding variants): CHINESE POSTMAN, where one asks for a minimum-cost tour traversing all edges of a graph at least once; RURAL POSTMAN, which generalizes CHINESE POSTMAN in the sense that only a subset of the edges has to be visited; and CAPACITATED ARC ROUTING, representing the most general arc routing problem in this chapter, allows more than one vehicle to be used to traverse the edges.