New Results in Finding Common Neighborhoods in Massive Graphs in the Data Streaming Model

Raffaele Giancarlo, Racz, Buchsbaum, Raffaele Giancarlo

Risultato della ricerca: Articlepeer review

3 Citazioni (Scopus)

Abstract

We consider the problem of finding pairs of vertices that share large commonneighborhoods in massive graphs. We give lower bounds for randomized, two-sided erroralgorithms that solve this problem in the data-stream model of computation. Our resultscorrect and improve those of Buchsbaum, Giancarlo, and Westbrook [On finding commonneighborhoods in massive graphs, Theoretical Computer Science, 299 (1–3) 707–718(2004)]
Lingua originaleEnglish
pagine (da-a)302-309
Numero di pagine8
RivistaTheoretical Computer Science
Volume407
Stato di pubblicazionePublished - 2008

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • ???subjectarea.asjc.1700.1700???

Fingerprint Entra nei temi di ricerca di 'New Results in Finding Common Neighborhoods in Massive Graphs in the Data Streaming Model'. Insieme formano una fingerprint unica.

Cita questo