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
Страницы310-323
Число страниц14
DOI
СостояниеОпубликовано - 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
Период20.07.201122.07.2011

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

Цитировать