Stefan Funke
Abstract
For a directed graph G with vertex set V we call a subset C ⊆ V a k-(All-)Path Cover if C contains a node from any path consisting of k nodes. This paper considers the problem of constructing small k-Path Covers in the context of road networks with millions of nodes and edges. In many application scenarios the set C and its induced overlay graph constitute a very compact synopsis of G which is the basis for the currently fastest data structure for personalized shortest path queries, visually pleasing overlays of subsampled paths, and efficient reporting, retrieval and aggregation of associated data in spatial network databases. Apart from a theoretical investigation of the problem, we provide efficient algorithms that produce very small k-Path Covers for large real-world road networks (with a posteriori guarantees via instance-based lower bounds).
- I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck. Vc-dimension and shortest path algorithms. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 690--699. Springer, 2011. Google Scholar
Digital Library
- I. Abraham, D. Delling, A. V. Goldberg, and R. F. Werneck. A hub-based labeling algorithm for shortest paths in road networks. In Symposium on Experimental Algorithms (SEA), pages 230--241. Springer, 2011. Google ScholarDigital Library
- H. Bast, S. Funke, P. Sanders, and D. Schultes. Fast routing in road networks using transit nodes. Science, 316(5824):566, 2007.Google ScholarCross Ref
- B. Bresar, F. Kardos, J. Katreniĉ and G. Semanisin. Minimum k-path vertex cover. Discrete Applied Mathematics, 159(12):1189--1195, 2011. Google ScholarDigital Library
- H. Brönnimann and M. T. Goodrich. Almost optimal set covers in finite vc-dimension. Discrete & Computational Geometry, 14(1):463--479, 1995.Google ScholarDigital Library
- D. Delling, A. V. Goldberg, T. Pajor, and R. F. F. Werneck. Customizable route planning. In P. M. Pardalos and S. Rebennack, editors, Symposium on Experimental Algorithms (SEA), pages 376--387. Springer, 2011. Google ScholarDigital Library
- S. Funke and S. Storandt. Polynomial-time construction of contraction hierarchies for multi-criteria objectives. In Algorithm Engineering and Experiments (ALENEX), pages 41--54. SIAM, 2013.Google ScholarCross Ref
- R. Geisberger, P. Sanders, D. Schultes, and C. Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 46(3):388--404, 2012. Google ScholarDigital Library
- R. J. Gutman. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Algorithm Engineering and Experiments (ALENEX), pages 100--111, 2004.Google Scholar
- D. Haussler and E. Welzl. Epsilon-nets and simplex range queries. In Symposium on Computational Geometry (SCG), pages 61--71, New York, NY, USA, 1986. ACM. Google ScholarDigital Library
- N. Ruan, R. Jin, and Y. Huang. Distance preserving graph simplification. CoRR, abs/1110.0517, 2011. Google ScholarDigital Library
- Y. Tao, C. Sheng, and J. Pei. On k-skip shortest paths. In ACM SIGMOD, pages 421--432. ACM, 2011. Google ScholarDigital Library
- V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264--280, 1971.Google ScholarCross Ref
Recommendations
Paired many-to-many disjoint path covers in faulty hypercubes
A paired many-to-many k-disjoint path cover (k-DPC for short) of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all the vertices of the graph. Extending the notion of DPC, we define a paired many-to-many bipartite k-...
Path covers of bubble-sort star graphs
AbstractThe distributed computing or parallel computing system uses an interconnection network as a topology structure to connect a large number of processors. The disjoint paths of interconnection networks are related to parallel computing and the fault ...
Many-to-many two-disjoint path covers in cylindrical and toroidal grids
A many-to-many k -disjoint path cover of a graph joining two disjoint vertex sets S and T of equal size k is a set of k vertex-disjoint paths between S and T that altogether cover every vertex of the graph. The many-to-many k -disjoint path cover is ...
Comments