MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Mehlhorn, Kurt
Ziegelmann, Mark		dblp
dblp
Editor(s):
Paterson, Mikedblp
BibTeX cite key*:
MehlhornZiegelmann2000
Title, Booktitle
Title*:
Resource Constrained Shortest Paths
Booktitle*:
Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
Event, URLs
Conference URL::
http://www.mpi-sb.mpg.de/~conf2000/esa2000/
Downloading URL:
Event Address*:
Saarbrücken, Germany
Language:
English
Event Date*
(no longer used):
September, 5-8
Organization:
Event Start Date:
5 September 2000
Event End Date:
8 September 2000
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1879
Number:
Month:
September
Pages:
326-337
Year*:
2000
VG Wort Pages:
ISBN/ISSN:
3-540-41004-X
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Keywords:
constrained shortest path
HyperLinks / References / URLs:
http://dblp.uni-trier.de/rec/bibtex/conf/esa/MehlhornZ00
Download
Access Level:
Intranet

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{MehlhornZiegelmann2000,
AUTHOR = {Mehlhorn, Kurt and Ziegelmann, Mark},
 EDITOR = {Paterson, Mike},
 TITLE = {Resource Constrained Shortest Paths},
 BOOKTITLE = {Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)},
 PUBLISHER = {Springer},
 YEAR = {2000},
 VOLUME = {1879},
 PAGES = {326--337},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Saarbr{\"u}cken, Germany},
 MONTH = {September},
 ISBN = {3-540-41004-X},
}

Entry last modified by Anja Becker, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Mark Ziegelmann		Created
01/16/2001 10:54:07
Revisions
10.
9.
8.
7.
6.		Editor(s)
Anja Becker
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
04.01.2008 15:57:33
01.09.2006 15:23:55
30.08.2006 16:45:02
30.08.2006 16:42:41
20.06.2006 11:55:58