论文标题
偏心率查询以及使用轮毂标签
Eccentricity queries and beyond using Hub Labels
论文作者
论文摘要
集线器标记方案是用于计算道路网络和其他大型复杂网络距离的流行方法，通常会在几微秒内回答数百万边缘的图形的查询。在这项工作中，我们研究了远程查询以外的算法应用。我们专注于偏心率查询和远程查询，对于有针对性的加权图上的这些问题的几个版本，这部分是由于它们在设施位置问题中的重要性而引起的。在负面，我们通过“细颗粒”复杂性的标准构建体显示了上述上述问题的条件下限。但是，当集线器标签具有sublogarithmic尺寸时，情况会有所不同。确实，给定最大标签大小$ \ leq k $的集线器标签，在对总计$ 2^{{o}（k）} \ cdot | v |^{1+o（1）$ time进行预处理后，我们可以计算任何偏心和距离的距离，并计算$ 2^^{o}的偏心和距离。 | v |^{o（1）} $时间。它也可以应用于某些拓扑指数的快速全球计算。最后，作为我们方法的副产品，在任何具有有界扩展的未加权的固定类别的未加权图上，我们可以确定同类中$ n $ vertex Graph的直径在$ f（k）\ cdot n^{1+o（1+o（1）} $中，最多是$ k $ in $ k $ f（k）\ cdot n^{1+o（1）$ f $ f $。
Hub labeling schemes are popular methods for computing distances on road networks and other large complex networks, often answering to a query within a few microseconds for graphs with millions of edges. In this work, we study their algorithmic applications beyond distance queries. We focus on eccentricity queries and distance-sum queries, for several versions of these problems on directed weighted graphs, that is in part motivated by their importance in facility location problems. On the negative side, we show conditional lower bounds for these above problems on unweighted undirected sparse graphs, via standard constructions from "Fine-grained" complexity. However, things take a different turn when the hub labels have a sublogarithmic size. Indeed, given a hub labeling of maximum label size $\leq k$, after pre-processing the labels in total $2^{{O}(k)} \cdot |V|^{1+o(1)}$ time, we can compute both the eccentricity and the distance-sum of any vertex in $2^{{O}(k)} \cdot |V|^{o(1)}$ time. It can also be applied to the fast global computation of some topological indices. Finally, as a by-product of our approach, on any fixed class of unweighted graphs with bounded expansion, we can decide whether the diameter of an $n$-vertex graph in the class is at most $k$ in $f(k) \cdot n^{1+o(1)}$ time, for some "explicit" function $f$.
