54 citations · 138 across the 46 of their papers we have counts for
Showing 2016 · cs.DSShow all
2 papers · 2 filters
cs.DS2016★ 5 cited
A Local Algorithm for Constructing Spanners in Minor-Free Graphs
Reut Levi, Dana Ron, Ronitt Rubinfeld
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider this problem in the setting of local algorithms: one wants to quickly determine…
cs.DS2016★ 5 cited
Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation
Maryam Aliakbarpour, Amartya Shankha Biswas, Themistoklis Gouleakis +3
We study the problem of estimating the value of sums of the form when one has the ability to sample with probability proportional…