TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 30.05.2013



zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Some Algorithmic Challenges in Arc Routing

Dipl.-Inf. Manuel Sorge (TU Berlin)

Arc Routing problems occur naturally in many logistic tasks like delivering mail, garbage disposal, street
sweeping and snow plowing. Such a task is formulated, for example, in the Chinese Postman problem
where, given an edge-weighted graph, one searches for a minimum-weight tour that visits all edges in
the graph. In this simple form, Chinese Postman is solvable in polynomial time, but many variants
that arise in applications yield NP-hard problems. Yet, despite the practical relevance, the literature on
parameterized complexity of Arc Routing problems is rather sparse. We give a brief survey of the known
(parameterized) complexity results and identify some interesting open questions. In particular, we briefly
report on our theoretical and empirical studies related to the Rural Postman problem.

This is joint work with René van Bevern, Rolf Niedermeier, and Mathias Weller.

30.05.2013 16:15
Manuel Sorge
TEL 512

Back to the research colloquium site.



Schnellnavigation zur Seite über Nummerneingabe