Literatur vom gleichen Autor/der gleichen Autor*in
plus bei Google Scholar

Bibliografische Daten exportieren
 

Euler is standing in line

Titelangaben

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