New Results in Finding Common Neighborhoods in Massive Graphs in the Data Streaming Model
- Autori: AL BUCHSBAUM; GIANCARLO R; B RAKZ
- Anno di pubblicazione: 2008
- Tipologia: Articolo in rivista (Articolo in rivista)
- Parole Chiave: Algorithms, Theoretical Computer Scienced
- OA Link: http://hdl.handle.net/10447/40091
Abstract
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)]