Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Mehlhorn, Kurt
Ziegelmann, Mark

dblp
dblp



Editor(s):

Paterson, Mike

dblp



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

URL of the conference:

http://www.mpi-sb.mpg.de/~conf2000/esa2000/

URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 AM
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