Highway Dimension, Shortest Paths, and Provably Efficient Algorithms
Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. 2010. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 782-793.
- グラフの Highway Dimension が h であるとは
- 任意の r > 0, 任意の頂点 u に対し，
- u から距離 4r の頂点の集合を B として，
- B の部分集合 S であって，以下を満たすものが存在
- |S| ≦ h
- 任意の頂点 v, w ∈ B に対し，距離が r より大きく最短路が B に含まれる場合，その最短路は S を通る
- (r, k)-SPC (Shortest Path Cover) とは
- 集合 C であって，以下を満たすもの
- 長さが r より大きく 2r 以下の任意の最短路について，それは C を通る
- 任意の頂点 u について，u から距離 2r 以下の集合 C 内の頂点は k 個以下
- 集合 C であって，以下を満たすもの
- 定理
- G の Highway Dimension が h ならば，任意の r に対し (r, h)-SPC 存在
- highway dimension が小さいことを仮定すると今までのヒューリスティクスを説明できる
