# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford

##### Locator

There are no locators available

##### Fulltext (public)

arXiv:1509.09047.pdf

(Preprint), 431KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Friedrichs, S., & Lenzen, C. (2015). Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford. Retrieved from http://arxiv.org/abs/1509.09047.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0029-4A48-B

##### Abstract

A \emph{metric tree embedding} of expected \emph{stretch $\alpha$} maps a
weighted $n$-node graph $G = (V, E, \omega)$ to a weighted tree $T = (V_T, E_T,
\omega_T)$ with $V \subseteq V_T$ such that $\operatorname{dist}(v, w, G) \leq
\operatorname{dist}(v, w, T)$ and $\E[\operatorname{dist}(v, w, T)] \leq \alpha
\operatorname{dist}(v, w, G)$ for all $v, w \in V$. Such embeddings are highly
useful for designing fast approximation algorithms, as many hard problems are
easy to solve on tree instances. However, to date the best parallel
$\operatorname{polylog} n$ depth algorithm that achieves an asymptotically
optimal expected stretch of $\alpha \in \operatorname{O}(\log n)$ requires
$\operatorname{\Omega}(n^2)$ work and requires a metric as input.
In this paper, we show how to achieve the same guarantees using
$\operatorname{\tilde{O}}(m^{1+\epsilon})$ work, where $m$ is the number of
edges of $G$ and $\epsilon > 0$ is an arbitrarily small constant. Moreover, one
may reduce the work further to $\operatorname{\tilde{O}}(m + n^{1+\epsilon})$,
at the expense of increasing the expected stretch $\alpha$ to
$\operatorname{O}(\epsilon^{-1} \log n)$. Our main tool in deriving these
parallel algorithms is an algebraic characterization of a generalization of the
classic Moore-Bellman-Ford algorithm. We consider this framework, which
subsumes a variety of previous "Moore-Bellman-Ford-flavored" algorithms, to be
of independent interest.