Standard

A new view on Rural Postman based on Eulerian Extension and Matching. / Sorge, Manuel; Van Bevern, René; Niedermeier, Rolf et al.

In: Journal of Discrete Algorithms, Vol. 16, 01.10.2012, p. 12-33.

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

Harvard

Sorge, M, Van Bevern, R, Niedermeier, R & Weller, M 2012, 'A new view on Rural Postman based on Eulerian Extension and Matching', Journal of Discrete Algorithms, vol. 16, pp. 12-33. https://doi.org/10.1016/j.jda.2012.04.007

APA

Sorge, M., Van Bevern, R., Niedermeier, R., & Weller, M. (2012). A new view on Rural Postman based on Eulerian Extension and Matching. Journal of Discrete Algorithms, 16, 12-33. https://doi.org/10.1016/j.jda.2012.04.007

Vancouver

Sorge M, Van Bevern R, Niedermeier R, Weller M. A new view on Rural Postman based on Eulerian Extension and Matching. Journal of Discrete Algorithms. 2012 Oct 1;16:12-33. doi: 10.1016/j.jda.2012.04.007

Author

Sorge, Manuel ; Van Bevern, René ; Niedermeier, Rolf et al. / A new view on Rural Postman based on Eulerian Extension and Matching. In: Journal of Discrete Algorithms. 2012 ; Vol. 16. pp. 12-33.

BibTeX

@article{9186818e21984d65b0e5c2b031012c60,
title = "A new view on Rural Postman based on Eulerian Extension and Matching",
abstract = "We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized equivalence between Rural Postman and Eulerian Extension, a natural arc addition problem in directed multigraphs. We indicate the NP-hardness of the introduced matching problem. In particular, we use the matching problem to make partial progress towards answering the open question about the parameterized complexity of Rural Postman with respect to the parameter {"}number of weakly connected components in the graph induced by the required arcs{"}. This is a more than thirty years open and long-neglected question with significant practical relevance.",
keywords = "Arc addition, Arc routing, Chinese postman, Parameterized complexity",
author = "Manuel Sorge and {Van Bevern}, Ren{\'e} and Rolf Niedermeier and Mathias Weller",
year = "2012",
month = oct,
day = "1",
doi = "10.1016/j.jda.2012.04.007",
language = "English",
volume = "16",
pages = "12--33",
journal = "Journal of Discrete Algorithms",
issn = "1570-8667",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - A new view on Rural Postman based on Eulerian Extension and Matching

AU - Sorge, Manuel

AU - Van Bevern, René

AU - Niedermeier, Rolf

AU - Weller, Mathias

PY - 2012/10/1

Y1 - 2012/10/1

N2 - We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized equivalence between Rural Postman and Eulerian Extension, a natural arc addition problem in directed multigraphs. We indicate the NP-hardness of the introduced matching problem. In particular, we use the matching problem to make partial progress towards answering the open question about the parameterized complexity of Rural Postman with respect to the parameter "number of weakly connected components in the graph induced by the required arcs". This is a more than thirty years open and long-neglected question with significant practical relevance.

AB - We provide a new characterization of the NP-hard arc routing problem Rural Postman in terms of a constrained variant of minimum-weight perfect matching on bipartite graphs. To this end, we employ a parameterized equivalence between Rural Postman and Eulerian Extension, a natural arc addition problem in directed multigraphs. We indicate the NP-hardness of the introduced matching problem. In particular, we use the matching problem to make partial progress towards answering the open question about the parameterized complexity of Rural Postman with respect to the parameter "number of weakly connected components in the graph induced by the required arcs". This is a more than thirty years open and long-neglected question with significant practical relevance.

KW - Arc addition

KW - Arc routing

KW - Chinese postman

KW - Parameterized complexity

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

U2 - 10.1016/j.jda.2012.04.007

DO - 10.1016/j.jda.2012.04.007

M3 - Article

AN - SCOPUS:84865483427

VL - 16

SP - 12

EP - 33

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

SN - 1570-8667

ER -

ID: 22341145