Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF D1 Publications :: Thesis :: Ziegelmann, Mark


MPI-INF D1 Publications
Show all entries of:this year (2019)last year (2018)two years ago (2017)Open in Notes
Action:login to update

Thesis - Doctoral dissertation | @PhdThesis | Doktorarbeit


Author
Author(s)*:Ziegelmann, Mark
BibTeX citekey*:Ziegelmann2001
Language:English

Title, School
Title*:Constrained Shortest Paths and Related Problems
School:Universität des Saarlandes
Type of Thesis*:Doctoral dissertation
Month:July
Year:2001


Note, Abstract, Copyright
LaTeX Abstract:The classical shortest path problem, to find a path

of minimal cost between two nodes in a graph, is efficiently solvable
in polynomial time. However, in many applications we also have additional
budget or resource constraints on a path. This problem is known as
constrained shortest path problem and unfortunately belongs to the
class of ``hard''
problems for which no polynomial time algorithm is known.
In this thesis, we propose a 2-step method for the constrained shortest
path problem. We first solve
a relaxation to get upper and lower bounds and then close the gap with
clever path ranking to
obtain the exact solution. We compare different old and new methods
both theoretically and experimentally.
The 2-step method also works for a more general class of
constrained network optimization problems. We illustrate the
generic approach using several examples. We have also developed
a software package {\sc Cnop} that provides this generic 2-step
approach as well as all state of the art algorithms for
constrained shortest paths.

HyperLinks / References / URLs:http://frweb.cs.uni-sb.de/dissdaten/Mark-Ziegelmann-Prof.%20Dr.%20Kurt%20Mehlhorn.pdf
Download Access Level:Public
Download File(s):

Referees, Status, Dates
1. Referee:Prof. Dr. Kurt Mehlhorn
2. Referee:Prof. Dr. Ulrich Lauther
Supervisor:Prof. Dr. Kurt Mehlhorn
Status:Completed
Date Kolloquium:30 July 2001
Chair Kolloquium:Prof. Dr. Raimund Seidel

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:
@PHDTHESIS{Ziegelmann2001,
AUTHOR = {Ziegelmann, Mark},
TITLE = {Constrained Shortest Paths and Related Problems},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {2001},
TYPE = {Doctoral dissertation}
MONTH = {July},
}





Entry last modified by Uwe Brahm, 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
07/25/2001 02:24:47 PM
Revision
1.
0.


Editor
Uwe Brahm
Mark Ziegelmann


Edit Date
05/05/2007 09:20:14 AM
25/07/2001 14:24:47