Customizable Contraction Hierarchies
We consider the problem of quickly computing shortest paths in weighted graphs given auxiliary data derived in an expensive preprocessing phase. By adding a fast weight-customization phase, we extend Contraction Hierarchies by Geisberger et al to support the three-phase workflow introduced by Delling et al. Our Customizable Contraction Hierarchies use nested dissection orders as suggested by Bauer et al. We provide an in-depth experimental analysis on large road and game maps that clearly shows that Customizable Contraction Hierarchies are a very practicable solution in scenarios where edge weights often change.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Capturing Logical Structure of Visually Structured Documents with Multimodal Transition Parser
While many NLP pipelines assume raw, clean texts, many texts we encounter in the wild, including a vast majority of legal documents, are not so clean, with many of them being visually structured documents (VSDs) such as …
Boundary DetectionEfficient and Reconfigurable Optimal Planning in Large-Scale Systems Using Hierarchical Finite State Machines
In this paper, we consider a planning problem for a large-scale system modelled as a hierarchical finite state machine (HFSM) and develop a control algorithm for computing optimal plans between any two states. The contro…
Efficient Planning in Large-scale Systems Using Hierarchical Finite State Machines
We consider optimal planning in a large-scale system formalised as a hierarchical finite state machine (HFSM). A planning algorithm is proposed computing an optimal plan between any two states in the HFSM, consisting of …
Automatically Differentiable Nonlinear Tensor Networks (ADNTNs) for Exponential Parameter Compression of Deep Neural Networks
Large deep neural networks are costly to store and deploy because inference must move and evaluate many parameters. This paper studies \emph{Automatically Differentiable Nonlinear Tensor Networks} (ADNTNs), compact diffe…
On the Link between Partial Meet, Kernel, and Infra Contraction and its Application to Horn Logic
Standard belief change assumes an underlying logic containing full classical propositional logic. However, there are good reasons for considering belief change in less expressive logics as well. In this paper we build on…