A New Efficient Construction on Probabilistic Tree Embeddings.
Guy E. Blelloch, Yan Gu, Yihan Sun · arXiv (Cornell University) · 2016
In this paper we describe a simple and efficient algorithm to construct FRT embeddings (optimal probabilistic tree embeddings) on graphs. For a graph with $n$ vertices and $m$ edges the algorithm runs in $O(m\log n+n\log^2 n)$ time. With the efficient FRT construction, we show that FRT trees are Ramsey partitions with asymptotically tight bound, and we give tighter bounds on coefficient than previous Ramsey partitions, hence improving other results on a series of distance oracles.