RECORD
Isometric embeddings in trees and their use in the diameter problem
Data Structures and Algorithms · Submitted 29 Oct 2020
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim 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.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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 $\omega(\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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | result 0.71 | 0.95 | 0.63 | asserted 1.00 |
| s1 | 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 $\omega(\log{n})$ spanning trees. | interpretation 0.79 | 0.69 | 0.13 | asserted 0.98 |
| s2 | 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. | result 0.86 | 0.89 | 0.15 | asserted 1.00 |
| s3 | 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). | result 0.36 | 0.88 | 0.13 | asserted 0.91 |
| s4 | The existence of embeddings in the Cartesian product of finitely many trees has been thoroughly investigated for cube-free median graphs. | background 1.00 | 0.05 | 0.04 | asserted 1.00 |
| s5 | We give the first-known quasi linear-time algorithm for computing the diameter within this graph class. | contribution 0.85 | 0.95 | 0.25 | asserted 1.00 |
| s6 | It does not require an embedding in a product of trees to be given as part of the input. | contribution 0.59 | 0.84 | 0.06 | asserted 1.00 |
| s7 | 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. | contribution 0.83 | 0.96 | 0.06 | asserted 1.00 |
| s8 | We combine the latter technical contribution, of independent interest, with a recent distance-labeling scheme that was designed for cube-free median graphs. | method 0.91 | 0.79 | 0.05 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
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 $\omega(\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.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.