zbMATH — the first resource for mathematics

The complexity of arc routing problems. (English) Zbl 1377.90114
Corberán, Ángel et al., Arc routing. Problems, methods, and applications. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); Philadelphia, PA: Mathematical Optimization Society (ISBN 978-1-61197-366-2/pbk). MOS-SIAM Series on Optimization 20, 19-52 (2014).
This book chapter consists of roughly 30 pages and surveys complexity issues of three arc routing problems, namely the Chinese postman problem, the rural postman problem and capacitated arc routing. After giving some introductory remarks on Eulerian graphs and complexity issues, the Chinese postman problem is discussed most intensively: the classical and the mixed Chinese postman problem, comments on the hardness, tractability and approximability. Then some further variants are briefly discussed such as windy costs, edge hierarchies and precedence relations or multiple postmen. For the second and third types of problems, short sub-sections about the classical complexity, the approximability and the parameterized complexity are presented. The sections of this chapter also formulate some interesting open problems. The chapter finishes with some concluding remarks and an outlook.
For the entire collection see [Zbl 1322.90006].

90C60 Abstract computational complexity for mathematical programming problems
90C35 Programming involving graphs or networks
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
68Q25 Analysis of algorithms and problem complexity
90C27 Combinatorial optimization