Home News About Us Contact Contributors Disclaimer Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Display Documents



ID: 344447.0, MPI für Informatik / Algorithms and Complexity Group
Resource Constrained Shortest Paths
Authors:Mehlhorn, Kurt; Ziegelmann, Mark
Editors:Paterson, Mike
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2000
Title of Proceedings:Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
Start Page:326
End Page:337
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Saarbrücken, Germany
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2000-09-05
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2008-01-04
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-7B769F17BCB8113EC12569D6003664F6-...
ISBN:3-540-41004-X
Full Text:
Sorry, no privileges
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.