54 citations · 101 across the 30 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.DS2015★ 1 cited
Local Computation Algorithms for Graphs of Non-Constant Degrees
Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee
In the model of \emph{local computation algorithms} (LCAs), we aim to compute the queried part of the output by examining only a small (sublinear) portion of the input. Many recent…
math.CO2015
Constructing Near Spanning Trees with Few Local Inspections
Reut Levi, Guy Moshkovitz, Dana Ron +2
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following var…