SHORTEST PATHS ON DYNAMIC GRAPHS: A SURVEY
ABSTRACT This paper provides an overview of the state-of-the art and the current research trends concerning shortest paths problem on dynamic graphs. The discussion is divided in two main topics: reoptimization and time-dependent shortest paths. Reoptimization consists in the solution of a sequence of shortest path problems in which each instance slightly differs from the previous one. The reoptimization tackles this problem wisely using information stored in an optimal solution previously computed. On the other hand, shortest path problems on time-dependent graphs are characterized by a weight function which not only depends upon the arcs but changes in time according to a certain time horizon.
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Digital revista |
| Language: | English |
| Published: |
Sociedade Brasileira de Pesquisa Operacional
2017
|
| Online Access: | http://old.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382017000300487 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|