de.mpg.escidoc.pubman.appbase.FacesBean
English
 
HelpDisclaimerContact usLogin
  Advanced SearchBrowse
  1. View item

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsStatisticsRevisionsRelease HistoryDetails
  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

 

show allhide all

Basic

show hide
Bookmark this item: http://pubman.mpdl.mpg.de/pubman/item/escidoc:1330800:2
Genre: Conference Paper

Files

show Files
hide Files
:
153.pdf (Publisher version), 108KB
Description:
-
Visibility:
Private (embargoed till )
MIME-Type / Checksum:
application/pdf
Copyright Date:
-
Copyright Info:
-
License:
-
:
Mehlhorn153.pdf (Publisher version), 121KB
Description:
-
Visibility:
Private (embargoed till )
MIME-Type / Checksum:
application/pdf
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, escidoc: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
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 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

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: -