Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 18 von 40
Zurück zur Trefferliste

Euler is Standing in Line

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-3947
  • 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 an approximation algorithm on general graphs with a performance of~$9/4$. For trees we improve the performance to~$5/3$.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Dietrich Hauptmeier, Sven Krumke, Jörg Rambau, Hans-Christoph Wirth.
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Eulerian Cycle; NP-completeness; elevator system; polynomial-time approximation algorithms; stacker-crane problem; vehicle routing
MSC-Klassifikation:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) [See also 68Q85]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
Datum der Erstveröffentlichung:03.03.1999
Schriftenreihe (Bandnummer):ZIB-Report (SC-99-06)
ZIB-Reportnummer:SC-99-06
Verlagspublikation:Appeared in: Discrete Appl. Math. 113 (2001) 87-107. A prel. vers. appeared in: Proc. of the 25nd Intern. Workshop on Graph-Theoretic Concepts in Computer Science (WG'99), Lecture Notes in Computer Science, vol. 1665, Springer (1999) 42-54
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.