Name
Abstract | ||
|---|---|---|
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(mlog n+nlog^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. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Data Structures and Algorithms | Graph,Binary logarithm,Discrete mathematics,Combinatorics,Vertex (geometry),Probabilistic logic,Mathematics |
DocType | Volume | Citations |
Journal | abs/1605.04651 | 1 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guy E. Blelloch | 1 | 2927 | 207.30 |
| Yan Gu | 2 | 43 | 5.10 |
| Yihan Sun | 3 | 73 | 11.19 |