Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 15261719
DOI: 10.7155/jgaa.00270 The Shortcut Problem  Complexity and Algorithms Reinhard Bauer , Gianlorenzo D'Angelo , Daniel Delling , Andrea Schumm , and Dorothea Wagner Vol. 16, no. 2, pp. 447481, 2012. Regular paper Abstract We study a graphaugmentation 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 edgeminimal 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 ILPbased exact approaches and show how to stochastically evaluate a given shortcut assignment on graphs that are too large to do so exactly.

Submitted: March 2011. Reviewed: November 2011. Revised: April 2012. Accepted: June 2012. Final: July 2012. Published: August 2012. Communicated by Susanne Albers 
Journal of Graph Algorithms and Applications 