94 citations · 198 across the 10 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2011★ 5 cited
More Compact Oracles for Approximate Distances in Planar Graphs
Christian Sommer
Distance oracles are data structures that provide fast (possibly approximate) answers to shortest-path and distance queries in graphs. The tradeoff between the space requirements a…
cs.DS2011★ 20 cited
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs
Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer
A (1 + eps)-approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a di…
cs.DS2010
Exact Distance Oracles for Planar Graphs
Shay Mozes, Christian Sommer
We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any direc…