The Shortcut Problem - Complexity and Algorithms

Abstract : We study a graph-augmentation problem arising from a technique applied in recent approaches for route planning. Many such methods enhance the graph by inserting shortcuts, i.e., additional edges (u,v) such that the length of (u,v) is the distance from u to v. Given a weighted, directed graph G and a number c in Z, the shortcut problem asks how to insert c shortcuts into G such that the expected number of edges that are contained in an edge-minimal shortest path from a random node s to a random node t is minimal. In this work, we study the algorithmic complexity of the problem and give approximation algorithms for a special graph class. Further, we state ILP-based exact approaches and show how to stochastically evaluate a given shortcut assignment on graphs that are too large to do so exactly.
Type de document :
Article dans une revue
Journal of Graph Algorithms and Applications (JGAA), Brown University, 2012, 16 (2), <10.7155/jgaa.00270>
Liste complète des métadonnées


https://hal.inria.fr/hal-00728877
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : jeudi 6 septembre 2012 - 19:13:59
Dernière modification le : vendredi 7 septembre 2012 - 09:45:19
Document(s) archivé(s) le : vendredi 7 décembre 2012 - 03:43:51

Fichier

02-IJGAA.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Reinhard Bauer, Gianlorenzo D'Angelo, Daniel Delling, Andrea Schumm, Dorothea Wagner. The Shortcut Problem - Complexity and Algorithms. Journal of Graph Algorithms and Applications (JGAA), Brown University, 2012, 16 (2), <10.7155/jgaa.00270>. <hal-00728877>

Partager

Métriques

Consultations de
la notice

249

Téléchargements du document

225