TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 30.05.2013

isti-logo

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.

Date
Speaker
Location
Language
30.05.2013 16:15
Manuel Sorge
TEL 512
english/german

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe