SHORTEST PATHS ON DYNAMIC GRAPHS: A SURVEY

AUTOR(ES)

Ferone, Daniele, Festa, Paola, Napoletano, Antonio, Pastore, Tommaso

FONTE

Pesqui. Oper.

DATA DE PUBLICAÇÃO

2017-09

RESUMO

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.

Documentos Relacionados

• The public good game on graphs: can the pro-social behavior persist?
• Description of continuous data using bar graphs: a misleading approach
• Generalizating path and fan graphs: subcoloring and toughness
• k-shortest paths
• Insights into the quaternary association of proteins through structure graphs: a case study of lectins