at Google ScholarTitle 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: | 06 Oct 2025 12:09 |
| URI: | https://eref.uni-bayreuth.de/id/eprint/756 |