TY - JOUR

T1 - The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard, yet disconnectedness is manageable

AU - Afanasev, Vsevolod A.

AU - van Bevern, René

AU - Tsidulko, Oxana Yu

N1 - Funding Information: This work is funded by Mathematical Center in Akademgorodok, agreement No. 075-15-2019-1675 with the Ministry of Science and Higher Education of the Russian Federation . Publisher Copyright: © 2021 Elsevier B.V. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/3

Y1 - 2021/3

N2 - The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.

AB - The Hierarchical Chinese Postman Problem is finding a shortest traversal of all edges of a graph respecting precedence constraints given by a partial order on classes of edges. We show that the special case with connected classes is NP-hard even on orders decomposable into a chain and an incomparable class. For the case with linearly ordered (possibly disconnected) classes, we get 5/3-approximations and fixed-parameter algorithms by transferring results from the Rural Postman Problem.

KW - Approximation algorithm

KW - Arc routing

KW - Fixed-parameter algorithm

KW - NP-hardness

KW - Rural Postman Problem

KW - Temporal graphs

UR - http://www.scopus.com/inward/record.url?scp=85100767856&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2021.01.017

DO - 10.1016/j.orl.2021.01.017

M3 - Article

AN - SCOPUS:85100767856

VL - 49

SP - 270

EP - 277

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 2

ER -