Search-space size in contraction hierarchies
Search-space size in contraction hierarchies
复制标题
DOI：
10.1016/j.tcs.2016.07.003
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
Reinhard Bauer;Tobias Columbus;Ignaz Rutter;D. Wagner
中科院分区：
文献类型：
--
作者：
Reinhard Bauer;Tobias Columbus;Ignaz Rutter;D. Wagner
收缩层次是一种提高最短路径计算性能的加速技术，在实践中效果很好。尽管有令人信服的实际结果，仍然缺乏对这种行为的理论解释。在本文中，我们开发了一个理论框架，研究收缩层次结构中的搜索空间大小。我们证明了搜索空间的大小，仅依赖于输入图的结构参数，也就是说，它们是独立的边的长度上的第一界。为了实现这一点，我们建立了一个良好的研究消除游戏的连接。我们的界限适用于图与treewidthk，并允许小分隔符的任何小封闭类的图。对于树，我们证明了最大搜索空间大小可以有效地最小化，平均搜索空间大小可以有效地近似为2倍。我们证明了，在最坏情况下对边长度的假设下，我们的界与Abraham等人[1]最近的论文“VC-维数和最短路径算法”中的界相当，后者的分析也依赖于边长度。作为一个附带的结果，我们将他们的公路尺寸的概念（一个参数，被证明是小的，但在所有的实际情况下是未知的）与路径宽度的概念。这是公路尺寸与已知图形参数的第一个关系。
Contraction hierarchies are a speed-up technique to improve the performance of shortest-path computations, which works very well in practice. Despite convincing practical results, there is still a lack of theoretical explanation for this behavior.In this paper, we develop a theoretical framework for studying search space sizes in contraction hierarchies. We prove the first bounds on the size of search spaces that depend solely on structural parameters of the input graph, that is, they are independent of the edge lengths. To achieve this, we establish a connection with the well-studied elimination game. Our bounds apply to graphs with treewidthk, and to any minor-closed class of graphs that admits small separators. For trees, we show that the maximum search space size can be minimized efficiently, and the average size can be approximated efficiently within a factor of 2.We show that, under a worst-case assumption on the edge lengths, our bounds are comparable to those in the recent paper “VC-Dimension and Shortest Path Algorithms” of Abraham et al. [1], whose analysis depends also on the edge lengths. As a side result, we link their notion of highway dimension (a parameter that is conjectured to be small, but is unknown for all practical instances) with the notion of pathwidth. This is the first relation of highway dimension with a well-known graph parameter.