New results for finding common neighborhoods in massive graphs in the data stream model
We consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. We give lower bounds for randomized, two-sided error algorithms that solve this problem in the data-stream model of computation. Our results correct and improve those of Buchsbaum, Giancarlo, and Westbrook [On finding common neighborhoods in massive graphs, Theoretical Computer Science, 299 (1-3) 707-718 (2004)] (C) 2008 Elsevier B.V. All rights reserved.
graph algorithms for data streams extremal graph theory communication complexity space lower bounds