Compact oracles for reachability and approximate distances in planar digraphs

By Mikkel Thorup. Proceedings IEEE International Conference on Cluster Computing, 2001

350 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/0e195e13955a54d11bb2ba9cdea38845de942a98

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Exact Routing in Large Road Networks Using Contraction Hierarchies (2012, methodology): “A different hierarchical approach is proposed by [Thorup 2004] to answer queries accurate within a factor (1+ε) in time O(log log(nC) + 1/ε) on planar graphs with integer edge weights in a range from 0 to C.”
Engineering Route Planning Algorithms (2009, methodology): “The approach from [70] has recently been implemented and experimentally evaluated on a road network with one million nodes [52].”
Route Planning in Transportation Networks (2015, methodology): “Thorup [244] has improved the theoretical worst-case bound of Dijkstra’s algorithm to O(|A| + |V | log log min{|V | , C}), but the required data structure is rather involved and unlikely to be faster in practice.”
Reachability and distance queries via 2-hop labels (2002, background): “One such example is the family of directed planar graphs: Reachability or (1+2)-approximate shortest paths have worst-case 2-hop labels of size O(n log(2) n) (using some slight modification of a construction by Thorup [11]) whereas for exact-distances, there is a known Ω(n) lower-bound for any label”
Highway Hierarchies Hasten Exact Shortest Path Queries (2005, methodology): “Queries accurate within a factor (1 + ) can be answered in near constant time using O((n log n)/ ) space and preprocessing time [5].”
Reach for A*: Efficient Point-to-Point Shortest Path Algorithms (2006, methodology): “However, our algorithm is simpler and combines in a natural way with A∗ search, which yields significantly better query times.”
Computing the shortest path: A search meets graph theory (2005, neutral): “range 267,403 631,964 [34,371/[-107,-103 ] 330,024 793,681 [37,39]/[-123,-121] 563,992 1,392,202 [33,35]/[-120,-115] 588,940 1,370,273 [37,40]/[-92,-88] 639,821 1,522,485 [31,34]/[-98,-94] 1,235,735 2,856,831 [33,45]/[-130,-120] 2,219,925 5,244,506 [33,45]/[-110,-100] 2,263,758 5,300,035 [33,45]/[-1”