69 citations · 180 across the 26 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016
Efficient Construction of Probabilistic Tree Embeddings
Guy E. Blelloch, Yan Gu, Yihan Sun
In this paper we describe an algorithm that embeds a graph metric on an undirected weighted graph into a distribution of tree metrics such that for ev…
cs.DS2016★ 1 cited
Parallel Shortest-Paths Using Radius Stepping
Guy E. Blelloch, Yan Gu, Yihan Sun +1
The single-source shortest path problem (SSSP) with nonnegative edge weights is a notoriously difficult problem to solve efficiently in parallel---it is one of the graph problems s…
cs.DS2016★ 69 cited
Sorting with Asymmetric Read and Write Costs
Guy E. Blelloch, Jeremy T. Fineman, Phillip B. Gibbons +2
Emerging memory technologies have a significant gap between the cost, both in time and in energy, of writing to memory versus reading from memory. In this paper we present models a…