Resource Constrained Shortest Paths

Mehlhorn, Kurt; Ziegelmann, Mark

doi:10.1007/3-540-45253-2_30

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Resource Constrained Shortest Paths

MPS-Authors

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45802

Ziegelmann, Mark
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

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

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-3349-9

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.