Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
A New View on Rural Postman Based on Eulerian Extension and Matching
verfasst von : Manuel Sorge, René van Bevern, Rolf Niedermeier, Mathias Weller
Erschienen in: Combinatorial Algorithms
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.