New complexity results for time-constrained dynamical optimal path problems

Sebastian Kluge, Martin Brokate, Konrad Reif

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

In this paper, we consider time-dependent networks, and the task of computing cost-optimal paths, which are constrained to stay close to fastest paths. We derive pruning criteria, which significantly improve both the number of vertex-time pairs expanded during search and the memory required to ensure the correctness of any solution algorithm. We then prove new complexity results, which imply that the problem of computing constrained cost-optimal paths in a discrete-time setting is polynomially solvable for several graph and constraint classes.

Original languageEnglish
Pages (from-to)123-147
Number of pages25
JournalJournal of Graph Algorithms and Applications
Volume14
Issue number2
DOIs
StatePublished - 2010

Fingerprint

Dive into the research topics of 'New complexity results for time-constrained dynamical optimal path problems'. Together they form a unique fingerprint.

Cite this