Standard

The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard, yet disconnectedness is manageable. / Afanasev, Vsevolod A.; van Bevern, René; Tsidulko, Oxana Yu.

In: Operations Research Letters, Vol. 49, No. 2, 03.2021, p. 270-277.

Research output: Contribution to journal › Article › peer-review

Harvard

Afanasev, VA, van Bevern, R & Tsidulko, OY 2021, 'The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard, yet disconnectedness is manageable', Operations Research Letters, vol. 49, no. 2, pp. 270-277. https://doi.org/10.1016/j.orl.2021.01.017

APA

Afanasev, V. A., van Bevern, R., & Tsidulko, O. Y. (2021). The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard, yet disconnectedness is manageable. Operations Research Letters, 49(2), 270-277. https://doi.org/10.1016/j.orl.2021.01.017

Vancouver

Afanasev VA, van Bevern R, Tsidulko OY. The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard, yet disconnectedness is manageable. Operations Research Letters. 2021 Mar;49(2):270-277. doi: 10.1016/j.orl.2021.01.017

Author

Afanasev, Vsevolod A. ; van Bevern, René ; Tsidulko, Oxana Yu. / The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard, yet disconnectedness is manageable. In: Operations Research Letters. 2021 ; Vol. 49, No. 2. pp. 270-277.

BibTeX

@article{75e04a2ca56f4a50b54c3c1ca7e79604,
title = "The Hierarchical Chinese Postman Problem: The slightest disorder makes it hard, yet disconnectedness is manageable",
abstract = "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.",
keywords = "Approximation algorithm, Arc routing, Fixed-parameter algorithm, NP-hardness, Rural Postman Problem, Temporal graphs",
author = "Afanasev, {Vsevolod A.} and {van Bevern}, Ren{\'e} and Tsidulko, {Oxana Yu}",
note = "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: {\textcopyright} 2021 Elsevier B.V. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",
year = "2021",
month = mar,
doi = "10.1016/j.orl.2021.01.017",
language = "English",
volume = "49",
pages = "270--277",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier Science Publishing Company, Inc.",
number = "2",

}

RIS

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 -

ID: 27877056