Efficient Construction of Probabilistic Tree Embeddings
作者： Guy E. Blelloch , Yan Gu , Yihan Sun
DOI:
关键词:
摘要: In this paper we describe an algorithm that embeds a graph metric $(V, d_G) $ on an undirected weighted graph $ G=(V, E) $ into a distribution of tree metrics $(T, D_T) $ such …
arxiv.org
harvard.edu参考文章(19)
Raimund Seidel, Backwards Analysis of Randomized Geometric Algorithms Springer Berlin Heidelberg. pp. 37- 67 ,(1993) , 10.1007/978-3-642-58043-7_3
Christian Wulff-Nilsen, Approximate distance oracles with improved query time symposium on discrete algorithms. pp. 539- 549 ,(2013) , 10.5555/2627817.2627856
Edith Cohen, Size-Estimation Framework with Applications to Transitive Closure and Reachability Journal of Computer and System Sciences. ,vol. 55, pp. 441- 453 ,(1997) , 10.1006/JCSS.1997.1534
Noga Alon, Richard M. Karp, David Peleg, Douglas West, A Graph-Theoretic Game and its Application to the $k$-Server Problem SIAM Journal on Computing. ,vol. 24, pp. 78- 100 ,(1995) , 10.1137/S0097539792224474
Manor Mendel, Assaf Naor, Ramsey partitions and proximity data structures foundations of computer science. pp. 109- 118 ,(2006) , 10.1109/FOCS.2006.65
Yair Bartal, On approximating arbitrary metrices by tree metrics symposium on the theory of computing. pp. 161- 168 ,(1998) , 10.1145/276698.276725
Gary L. Miller, Richard Peng, Adrian Vladu, Shen Chen Xu, Improved Parallel Algorithms for Spanners and Hopsets acm symposium on parallel algorithms and architectures. pp. 192- 201 ,(2015) , 10.1145/2755573.2755574
Shiri Chechik, Approximate Distance Oracles with Improved Bounds symposium on the theory of computing. pp. 1- 10 ,(2015) , 10.1145/2746539.2746562
Philip N Klein, Sairam Subramanian, A Randomized Parallel Algorithm for Single-Source Shortest Paths Journal of Algorithms. ,vol. 25, pp. 205- 220 ,(1997) , 10.1006/JAGM.1997.0888
Jittat Fakcharoenphol, Satish Rao, Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics symposium on the theory of computing. ,vol. 69, pp. 448- 455 ,(2003) , 10.1145/780542.780608