Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

Euler is standing in line

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 Mathematics in Economy > Chair Mathematics in Economy - Univ.-Prof. Dr. Jörg Rambau
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics in Economy
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