Shortest-Path Queries in Static Networks

被引:170
作者
Sommer, Christian [1 ]
机构
[1] MIT, CSAIL, Cambridge, MA 02139 USA
关键词
Algorithms; Theory; Shortest path; shortest-path query; distance oracle; SPEED-UP TECHNIQUES; APPROXIMATE DISTANCE ORACLES; FINITE METRIC-SPACES; DECOMPOSITION ALGORITHM; SEPARATOR THEOREM; UNWEIGHTED GRAPHS; COMPACT ORACLES; PLANAR GRAPHS; ROAD NETWORKS; SMALL-WORLD;
D O I
10.1145/2530531
中图分类号
TP301 [理论、方法];
学科分类号
080201 [机械制造及其自动化];
摘要
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-path (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 problems are considered 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 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 arguable practical significance such as planar graphs and complex networks.
引用
收藏
页数:31
相关论文
共 260 条
[1]
Abraham I, 2012, LECT NOTES COMPUT SC, V7501, P24, DOI 10.1007/978-3-642-33090-2_4
[2]
Abraham I, 2011, LECT NOTES COMPUT SC, V6630, P230
[3]
Abraham I, 2011, LECT NOTES COMPUT SC, V6950, P404, DOI 10.1007/978-3-642-24100-0_39
[4]
Abraham I, 2011, LECT NOTES COMPUT SC, V6755, P690, DOI 10.1007/978-3-642-22006-7_58
[5]
Abraham I, 2010, PROC APPL MATH, V135, P782
[6]
Compact Name-Independent Routing with Minimum Stretch [J].
Abraham, Ittai ;
Gavoille, Cyril ;
Malkhi, Dahlia ;
Nisan, Noam ;
Thorup, Mikkel .
ACM TRANSACTIONS ON ALGORITHMS, 2008, 4 (03)
[7]
Abraham I, 2008, PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P363
[8]
Abraham Ittai, 2006, PODC, P188, DOI 10.1145/1146381.1146411
[9]
On the Bias of Traceroute Sampling: or, Power-Law Degree Distributions in Regular Graphs [J].
Achlioptas, Dimitris ;
Clauset, Aaron ;
Kempe, David ;
Moore, Cristopher .
JOURNAL OF THE ACM, 2009, 56 (04)
[10]
Agarwal R., 2013, PREPRINT