@misc{HauptmeierKrumkeRambauetal., author = {Hauptmeier, Dietrich and Krumke, Sven and Rambau, J{\"o}rg and Wirth., Hans-Christoph}, title = {Euler is Standing in Line}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3947}, number = {SC-99-06}, abstract = {In this paper we study algorithms for ``Dial-a-Ride'' transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and an approximation algorithm on general graphs with a performance of~\$9/4\$. For trees we improve the performance to~\$5/3\$.}, language = {en} }