5 citations · 16 across the 11 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.DS2015★ 2 cited
Non-Local Probes Do Not Help with Graph Problems
Mika Göös, Juho Hirvonen, Reut Levi +2
This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computi…
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…