Access to Data and Number of Iterations
Kook Jin Ahn, Sudipto Guha · 2015
In this paper we consider graph algorithms in models of computation where the space usage (random accessible storage, in addition to the read only input) is sublinear in the number of edges m and the access to input data is constrained. These questions arises in many natural settings, and in particular in the analysis of MapReduce or similar algorithms that model constrained parallelism with sublinear central processing. In SPAA 2011, Lattanzi etal. provided a O(1) approximation of maximum matching using O(p) rounds of iterative filtering via mapreduce and O(n1+1/p) space of central processing for a graph with n nodes and m edges.