Christian Sommer

ACM Computing Surveys, Volume 46, Issue 4

We consider the *point-to-point (approximate) shortest-path query problem*, which is the following generalization of the classical *single-source (SSSP)* and *all-pairs shortest paths (APSP)* problems: We are first presented with a *network* (*graph*). A so-called *preprocessing* algorithm may compute certain information (a *data structure* or *index*) to prepare for the next phase. After this preprocessing step, applications may ask shortest-path or distance *queries*, which should be answered as fast as possible.

Due to its many applications in areas such as transportation, networking, and social science, this problem has been considered by researchers from various communities (sometimes under different names): algorithm engineers construct fast *route planning* methods, database and information systems researchers investigate *materialization tradeoffs*, query processing on *spatial networks*, and *reachability queries*, and theoretical computer scientists analyze *distance oracles* and *sparse spanners*. Related questions are posed for *compact routing* and *distance labeling* schemes in networking and distributed computing and for *metric embeddings* in geometry as well.

In this survey, we review selected approaches, algorithms, and results on shortest-path queries from all these fields, with the main focus lying on the tradeoff between the index size and the query time. We survey methods for general graphs as well as specialized methods for restricted graph classes, in particular for those classes with arguably high practical significance such as planar graphs and complex networks.

@article{Som14, title = {Shortest-Path Queries in Static Networks}, author = {Christian Sommer}, journal = {ACM Computing Surveys}, volume = {46}, issue = {4}, pages = {45:1--31}, year = {2014}, url = {http://dx.doi.org/10.1145/2530531}, doi = {10.1145/2530531}, }

Official version

Local version (506.2 KB)

This survey is largely based on Chapter 3 of my Ph.D. thesis.

Home → Publications → Shortest-Path Queries in Static Networks