6533b856fe1ef96bd12b3157

RESEARCH PRODUCT

New results for finding common neighborhoods in massive graphs in the data stream model

A. L. BuchsbaumRaffaele GiancarloB. Racz

subject

Data streamDiscrete mathematicsGeneral Computer ScienceExtremal graph theorySpace lower boundsModel of computationCommunication complexityGraph theoryUpper and lower boundsTheoretical Computer ScienceExtremal graph theoryCombinatoricsGraph algorithms for data streamsAlgorithms Theoretical Computer SciencedGraph algorithmsCommunication complexityComputer Science(all)Mathematics

description

AbstractWe 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)]

yearjournalcountryeditionlanguage
2008-11-01Theoretical Computer Science
https://doi.org/10.1016/j.tcs.2008.06.056