A New View on Rural Postman Based on Eulerian Extension and Matching (Homepage of René van Bevern)

Manuel Sorge, René van Bevern, Rolf Niedermeier, and Mathias Weller:
A New View on Rural Postman Based on Eulerian Extension and Matching. In Proceedings of the 22nd International Workshop on Combinatorial Algorithms (IWOCA'11), Victoria, Canada, June 2011. Volume 7056 in Lecture Notes in Computer Science, pages 310–323, Springer.

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.

Download

The paper is availabe in PDF format.

BibTex Entry

For information on using BibTex in your LaTeX documents, refer to the chapter "Bibliography management" in the wikibook for LaTeX.


@inproceedings{SvBNW11a,
  Title = {A New View on Rural Postman Based on 
    Eulerian Extension and Matching},
  Author = {Manuel Sorge and Ren\'e van Bevern and
    Rolf Niedermeier and Mathias Weller},
  Booktitle = {Proceedings of the 22nd International Workshop
    on Combinatorial Algorithms (IWOCA'11)},
  Pages = {310--323},
  Year = {2011},
  Volume = {7056},
  Publisher = {Springer},
  Series = {LNCS},
}