Geodesic
The Shortcut Problem - Complexity and Algorithms
Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 447-481.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 ∈ Z > 0, 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. 
@article{JGAA_2012_16_2_a12,
     author = {Reinhard Bauer and Gianlorenzo D'Angelo and Daniel Delling and Andrea Schumm and Dorothea Wagner},
     title = {The {Shortcut} {Problem} - {Complexity} and {Algorithms}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {447--481},
     publisher = {mathdoc},
     volume = {16},
     number = {2},
     year = {2012},
     doi = {10.7155/jgaa.00270},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00270/}
}
TY  - JOUR
AU  - Reinhard Bauer
AU  - Gianlorenzo D'Angelo
AU  - Daniel Delling
AU  - Andrea Schumm
AU  - Dorothea Wagner
TI  - The Shortcut Problem - Complexity and Algorithms
JO  - Journal of Graph Algorithms and Applications
PY  - 2012
SP  - 447
EP  - 481
VL  - 16
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00270/
DO  - 10.7155/jgaa.00270
LA  - en
ID  - JGAA_2012_16_2_a12
ER  - 
%0 Journal Article
%A Reinhard Bauer
%A Gianlorenzo D'Angelo
%A Daniel Delling
%A Andrea Schumm
%A Dorothea Wagner
%T The Shortcut Problem - Complexity and Algorithms
%J Journal of Graph Algorithms and Applications
%D 2012
%P 447-481
%V 16
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00270/
%R 10.7155/jgaa.00270
%G en
%F JGAA_2012_16_2_a12
Reinhard Bauer; Gianlorenzo D'Angelo; Daniel Delling; Andrea Schumm; Dorothea Wagner. The Shortcut Problem - Complexity and Algorithms. Journal of Graph Algorithms and Applications, Tome 16 (2012) no. 2, pp. 447-481. doi : 10.7155/jgaa.00270. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00270/

Cité par Sources :