论文标题
最短的枚举问题
Shortest Distances as Enumeration Problem
论文作者
论文摘要
我们将最短距离（SSSD）和所有对最短距离（APSD）问题作为枚举问题（在未加权和整数加权图上）进行研究，这意味着元素$（u，v，v，d（u，v）$ - $ u $ and $ u $ and $ u $和$ v $是最短的距离（u，v）$ d（u，v），而不是生产和列表的一个。相对于预处理时间和延迟的RAM计算模型，该性能是在两个连续输出之间超过的最大时间。这种观点表明，特定类型的输出（例如，排除了不可访问的对$（u，v，\ infty）$，或排除自差$（u，u，u，0）$）和枚举顺序（例如，按距离对距离进行排序，对距离哑光的行为都没有效果，同时对他们的复杂性产生了巨大影响。 特别是，我们为APSD表明，随着平均程度的顺序延迟，无需输出限制的枚举可能是可能的。排除不可访问的对，或要求用距离排序的输出将此延迟增加到最高程度的顺序。此外，对于加权图，如果没有预处理或将自距离作为输出，则平均程度顺序的延迟也是不可能的。相比之下，对于SSSD，我们发现在没有预处理的情况下，最高程度的延迟是可以实现的，并且对于任何这些要求中的任何一个都是不可避免的。
We investigate the single source shortest distance (SSSD) and all pairs shortest distance (APSD) problems as enumeration problems (on unweighted and integer weighted graphs), meaning that the elements $(u, v, d(u, v))$ -- where $u$ and $v$ are vertices with shortest distance $d(u, v)$ -- are produced and listed one by one without repetition. The performance is measured in the RAM model of computation with respect to preprocessing time and delay, i.e., the maximum time that elapses between two consecutive outputs. This point of view reveals that specific types of output (e.g., excluding the non-reachable pairs $(u, v, \infty)$, or excluding the self-distances $(u, u, 0)$) and the order of enumeration (e.g., sorted by distance, sorted row-wise with respect to the distance matrix) have a huge impact on the complexity of APSD while they appear to have no effect on SSSD. In particular, we show for APSD that enumeration without output restrictions is possible with delay in the order of the average degree. Excluding non-reachable pairs, or requesting the output to be sorted by distance, increases this delay to the order of the maximum degree. Further, for weighted graphs, a delay in the order of the average degree is also not possible without preprocessing or considering self-distances as output. In contrast, for SSSD we find that a delay in the order of the maximum degree without preprocessing is attainable and unavoidable for any of these requirements.
