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)]
AL BUCHSBAUM, GIANCARLO R, B RAKZ (2008). New Results in Finding Common Neighborhoods in Massive Graphs in the Data Streaming Model. THEORETICAL COMPUTER SCIENCE, 407, 302-309 [10.1016/j.tcs.2008.06.056].
New Results in Finding Common Neighborhoods in Massive Graphs in the Data Streaming Model
GIANCARLO, Raffaele;
2008-01-01
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)]
| File | Dimensione | Formato | |
|---|---|---|---|
|
1-s2.0-S0304397508004337-main.pdf
Solo gestori archvio
Dimensione
720.84 kB
Formato
Adobe PDF
|
720.84 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
