## Title data

Grüne, Lars ; Junge, Oliver:

**An efficient algorithm for perturbed shortest path problems.**

*In:* Proceedings in Applied Mathematics and Mechanics.
Vol. 7
(December 2007)
Issue 1
.
- pp. 1025003-1025004.

ISSN 1617-7061

DOI: https://doi.org/10.1002/pamm.200700714

## Abstract in another language

We present an efficient algorithm for perturbed shortest paths problems that arise, e.g., in dynamic games. Via a min-max version of Dijkstra's algorithm we compute piecewise constant upper and lower bounds on the upper value function of the game. Convergence of the bounds in the limit of vanishing cell diameter can be proved. The method is numerically demonstrated on a simple 2d dynamic game, the homicidal chauffeur.

## Further data

Item Type: | Article in a journal |
---|---|

Refereed: | Yes |

Institutions of the University: | Faculties Faculties > Faculty of Mathematics, Physics und Computer Science Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics V (Applied Mathematics) Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematics V (Applied Mathematics) > Chair Mathematics V (Applied Mathematics) - Univ.-Prof. Dr. Lars Grüne |

Result of work at the UBT: | Yes |

DDC Subjects: | 500 Science 500 Science > 510 Mathematics |

Date Deposited: | 03 Mar 2021 12:36 |

Last Modified: | 23 Mar 2021 09:12 |

URI: | https://eref.uni-bayreuth.de/id/eprint/63630 |