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

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

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

3 Цитирования (Scopus)


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.

Язык оригиналаанглийский
Название основной публикацииCombinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers
Число страниц14
СостояниеОпубликовано - 28 нояб. 2011
Опубликовано для внешнего пользованияДа
Событие22nd International Workshop on Combinatorial Algorithms, IWOCA 2011 - Vancouver, BC, Канада
Продолжительность: 20 июл. 201122 июл. 2011

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том7056 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349


Конференция22nd International Workshop on Combinatorial Algorithms, IWOCA 2011
ГородVancouver, BC


Подробные сведения о темах исследования «A new view on rural postman based on Eulerian extension and matching». Вместе они формируют уникальный семантический отпечаток (fingerprint).