2013 · 10 citations · 5 references
ComputingComputer ScienceAlgorithmsComputational GeometryApproximation AlgorithmsGraph AlgorithmsShortest Path AlgorithmsConstrained Shortest PathsExact Shortest Path ComputationShortest Path ProblemsShortest Paths
Shortest path querying is a fundamental graph problem which is computationally quite challenging when operating over massive scale graphs. Recent results have addressed the problem of computing either exact or good approximate shortest path distances efficiently. Some of these techniques also return the path corresponding to the estimated shortest path distance fast.
5
The RDF-3X engine for scalable management of RDF data
Thomas Neumann, Gerhard Weikum · The VLDB Journal · 2009 · 639 citations · Full text
Mikkel Thorup, Uri Zwick · Journal of the ACM · 2005 · 618 citations
Fast and accurate estimation of shortest paths in large graphs
Andrey Gubichev, Srikanta Bedathur, Stephan Seufert et al. · 2010 · 149 citations
A sketch-based distance oracle for web-scale graphs
Atish Das Sarma, Sreenivas Gollapudi, Marc Najork et al. · 2010 · 120 citations
Shortest-path feasibility algorithms
Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg et al. · ACM Journal of Experimental Algorithmics · 2009 · 19 citations