bei Google ScholarTitelangaben
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
. - S. 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 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.
Weitere Angaben
| Publikationsform: | Aufsatz in einem Buch |
|---|---|
| Begutachteter Beitrag: | Ja |
| Institutionen der Universität: | Fakultäten Fakultäten > Fakultät für Mathematik, Physik und Informatik Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut > Lehrstuhl Wirtschaftsmathematik > Lehrstuhl Wirtschaftsmathematik - Univ.-Prof. Dr. Jörg Rambau Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut > Lehrstuhl Wirtschaftsmathematik |
| Titel an der UBT entstanden: | Nein |
| Themengebiete aus DDC: | 500 Naturwissenschaften und Mathematik > 510 Mathematik |
| Eingestellt am: | 06 Jun 2014 06:30 |
| Letzte Änderung: | 07 Jun 2016 11:22 |
| URI: | https://eref.uni-bayreuth.de/id/eprint/756 |