论文标题
树木中的等距嵌入及其在直径问题中的使用
Isometric embeddings in trees and their use in the diameter problem
论文作者
论文摘要
We prove that given a discrete space with $n$ points which is either embedded in a system of $k$ trees, or the Cartesian product of $k$ trees, we can compute all eccentricities in ${\cal O}(2^{{\cal O}(k\log{k})}(N+n)^{1+o(1)})$ time, where $N$ is the cumulative total order在所有这些$ k $树上。在强烈的指数假设下，这几乎是最佳的，即使在$ n $ vertex图的特殊情况下，嵌入在$ω（\ log {n}）$跨度树的系统中。但是，鉴于$ k $树的强产物中的这种嵌入，有一个更快的$ {\ cal o}（n + kn）$ - 用于此问题的时间算法。如果将这种嵌入为输入，则我们所有的积极结果都可以转变为图形和有限空间的近似算法，其中近似因子（分别，近似值常数）取决于嵌入的嵌入（respection fanst。有限的许多树木的笛卡尔产物中存在嵌入，已彻底研究了无立方体中间图。我们提供了用于计算此图类中直径的首个已知的准线性时间算法。它不需要在树木的产物中嵌入作为输入的一部分。在我们的途中，我们获得了$ n $ node $ t $，我们提出了一个数据结构，其中$ {\ cal o}（n \ log {n}）$预处理时间以计算$ {\ cal o}（k \ log^log^2 {n}）$的时间。我们将独立关注的后一种技术贡献与最新的距离标记方案相结合，该方案是为无立方体中值图设计的。
We prove that given a discrete space with $n$ points which is either embedded in a system of $k$ trees, or the Cartesian product of $k$ trees, we can compute all eccentricities in ${\cal O}(2^{{\cal O}(k\log{k})}(N+n)^{1+o(1)})$ time, where $N$ is the cumulative total order over all these $k$ trees. This is near optimal under the Strong Exponential-Time Hypothesis, even in the very special case of an $n$-vertex graph embedded in a system of $ω(\log{n})$ spanning trees. However, given such an embedding in the strong product of $k$ trees, there is a much faster ${\cal O}(N + kn)$-time algorithm for this problem. All our positive results can be turned into approximation algorithms for the graphs and finite spaces with a quasi isometric embedding in trees, if such embedding is given as input, where the approximation factor (resp., the approximation constant) depends on the distortion of the embedding (resp., of its stretch). The existence of embeddings in the Cartesian product of finitely many trees has been thoroughly investigated for cube-free median graphs. We give the first-known quasi linear-time algorithm for computing the diameter within this graph class. It does not require an embedding in a product of trees to be given as part of the input. On our way, being given an $n$-node tree $T$, we propose a data structure with ${\cal O}(n\log{n})$ pre-processing time in order to compute in ${\cal O}(k\log^2{n})$ time the eccentricity of any subset of $k$ nodes. We combine the latter technical contribution, of independent interest, with a recent distance-labeling scheme that was designed for cube-free median graphs.
