English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  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

Files

show Files
hide Files
:
153.pdf (Publisher version), 108KB
 
File Permalink:
-
Name:
153.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-
:
Mehlhorn153.pdf (Publisher version), 121KB
 
File Permalink:
-
Name:
Mehlhorn153.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Mehlhorn, Kurt1, Author           
Ziegelmann, Mark1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 2008-01-042000
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 344447
Other: Local-ID: C1256428004B93B8-7B769F17BCB8113EC12569D6003664F6-MehlhornZiegelmann2000
DOI: 10.1007/3-540-45253-2_30
BibTex Citekey: Mehlhorn-Ziegelmann_ESA2000
 Degree: -

Event

show
hide
Title: 8th Annual European Symposium on Algorithms
Place of Event: Saarbrücken, Germany
Start-/End Date: 2000-09-05 - 2000-09-08

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2000
  Subtitle : 8th Annual European Symposium
  Abbreviation : ESA 2000
Source Genre: Proceedings
 Creator(s):
Paterson, Mike1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 326 - 337 Identifier: ISBN: 978-3-540-41004-1

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 1879 Sequence Number: - Start / End Page: - Identifier: -