During the last years, speed-up techniques for Dijkstra’s algorithm have been developed that make the computation of shortest paths a matter of microseconds even on huge road networks. The most sophisticated methods enhance the graph by inserting shortcuts, i.e. additional edges, that represent shortest paths in the graph. Until now, all existing shortcut-insertion strategies are heuristics and no theoretical results on the topic are known. In this work, we formalize the problem of adding shortcuts as a graph augmentation problem, study the algorithmic complexity of the problem, give approximation algorithms and show how to stochastically evaluate a given shortcut assignment on graphs that are too big to evaluate it exactly.

The Shortcut Problem - Complexity and Approximation

D'ANGELO G;
2009

Abstract

During the last years, speed-up techniques for Dijkstra’s algorithm have been developed that make the computation of shortest paths a matter of microseconds even on huge road networks. The most sophisticated methods enhance the graph by inserting shortcuts, i.e. additional edges, that represent shortest paths in the graph. Until now, all existing shortcut-insertion strategies are heuristics and no theoretical results on the topic are known. In this work, we formalize the problem of adding shortcuts as a graph augmentation problem, study the algorithmic complexity of the problem, give approximation algorithms and show how to stochastically evaluate a given shortcut assignment on graphs that are too big to evaluate it exactly.
978-3-540-95890-1
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/20.500.12571/1268
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact