English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Resource Constrained Shortest Paths

Mehlhorn, K., & Ziegelmann, M. (2000). Resource Constrained Shortest Paths. In Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00) (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           
Paterson, Mike, Editor
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
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Saarbrücken, Germany
Start-/End Date: 2000-09-05

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 326 - 337 Identifier: ISBN: 3-540-41004-X

Source 2

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