A new view on rural postman based on Eulerian extension and matching

Manuel Sorge, René Van Bevern, Rolf Niedermeier, Mathias Weller

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

3 Citations (Scopus)

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 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.

Original languageEnglish
Title of host publicationCombinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers
Pages310-323
Number of pages14
DOIs
Publication statusPublished - 28 Nov 2011
Externally publishedYes
Event22nd International Workshop on Combinatorial Algorithms, IWOCA 2011 - Vancouver, BC, Canada
Duration: 20 Jul 201122 Jul 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7056 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Workshop on Combinatorial Algorithms, IWOCA 2011
CountryCanada
CityVancouver, BC
Period20.07.201122.07.2011

Fingerprint Dive into the research topics of 'A new view on rural postman based on Eulerian extension and matching'. Together they form a unique fingerprint.

Cite this