## Title data

Hauptmeier, Dietrich ; Krumke, Sven O. ; Rambau, Jörg ; Wirth, Hans-Christoph:

**Euler is standing in line.**

*In:*
Widmayer, Peter (Hrsg.): Graph-Theoretic Concepts in Computer Science : 25th international workshop, WG '99, Ascona, Switzerland, June 17 - 19, 1999 ; proceedings. -
Berlin
: Springer
,
1999
. - pp. 42-54
. - (Lecture Notes in Computer Science
; 1665
)

ISBN 3-540-66731-8

DOI: https://doi.org/10.1007/3-540-46784-X

## Abstract in another language

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 approximation algorithms general graphs and trees with performances of 9/4 and 5/3, respectively.

## Further data

Item Type: | Article in a book |
---|---|

Refereed: | Yes |

Institutions of the University: | Faculties Faculties > Faculty of Mathematics, Physics und Computer Science Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics > Chair Mathematical Economics - Univ.-Prof. Dr. Jörg Rambau Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics |

Result of work at the UBT: | No |

DDC Subjects: | 500 Science > 510 Mathematics |

Date Deposited: | 06 Jun 2014 06:30 |

Last Modified: | 07 Jun 2016 11:22 |

URI: | https://eref.uni-bayreuth.de/id/eprint/756 |