TY - GEN
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 - 2011/11/28
Y1 - 2011/11/28
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 it to make some partial progress towards answering the open question about the parameterized complexity of Rural Postman with respect to the number of weakly connected components in the graph induced by the required arcs. This is a more than thirty years open and long-time 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 it to make some partial progress towards answering the open question about the parameterized complexity of Rural Postman with respect to the number of weakly connected components in the graph induced by the required arcs. This is a more than thirty years open and long-time neglected question with significant practical relevance.
UR - http://www.scopus.com/inward/record.url?scp=81855225396&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-25011-8_25
DO - 10.1007/978-3-642-25011-8_25
M3 - Conference contribution
AN - SCOPUS:81855225396
SN - 9783642250101
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 310
EP - 323
BT - Combinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers
T2 - 22nd International Workshop on Combinatorial Algorithms, IWOCA 2011
Y2 - 20 July 2011 through 22 July 2011
ER -