TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 30.05.2013


Page Content

to Navigation

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.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe