| Euler is Standing in Line (2001) | |||||||||||||||
|
|||||||||||||||
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 nd 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 approximation algorithms for general graphs and trees with performances of 9=4 and 5=3, respectively. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||