Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Resource Constrained Shortest Paths

Mehlhorn, K., & Ziegelmann, M. (2000). Resource Constrained Shortest Paths. In M. Paterson (Ed.), Algorithms - ESA 2000 (pp. 326-337). Berlin, Germany: Springer.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3349-9 Versions-Permalink: https://hdl.handle.net/21.11116/0000-000E-455E-C
Genre: Konferenzbeitrag

Dateien

einblenden: Dateien
ausblenden: Dateien
:
153.pdf (Verlagsversion), 108KB
 
Datei-Permalink:
-
Name:
153.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-
:
Mehlhorn153.pdf (Verlagsversion), 121KB
 
Datei-Permalink:
-
Name:
Mehlhorn153.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Mehlhorn, Kurt1, Autor           
Ziegelmann, Mark1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: The resource constrained shortest path problem (CSP) asks for the computation
of a least cost path obeying a set of resource constraints. The problem is
NP-complete. We give theoretical and experimental results for CSP. In the
theoretical part we present the hull approach, a combinatorial algorithm
for solving a linear
programming relaxation and prove that it runs in polynomial time in the case of
one resource. In the experimental part we compare the hull approach to previous
methods for solving the LP relaxation and give an exact algorithm based on
the hull approach. We also compare our exact algorithm to previous
exact algorithms and approximation algorithms for the problem.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2008-01-042000
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 344447
Anderer: Local-ID: C1256428004B93B8-7B769F17BCB8113EC12569D6003664F6-MehlhornZiegelmann2000
DOI: 10.1007/3-540-45253-2_30
BibTex Citekey: Mehlhorn-Ziegelmann_ESA2000
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 8th Annual European Symposium on Algorithms
Veranstaltungsort: Saarbrücken, Germany
Start-/Enddatum: 2000-09-05 - 2000-09-08

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithms - ESA 2000
  Untertitel : 8th Annual European Symposium
  Kurztitel : ESA 2000
Genre der Quelle: Konferenzband
 Urheber:
Paterson, Mike1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 326 - 337 Identifikator: ISBN: 978-3-540-41004-1

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 1879 Artikelnummer: - Start- / Endseite: - Identifikator: -