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

DOI10.1016/J.TCS.2008.06.056zbMath1154.68109OpenAlexW2039019752MaRDI QIDQ955006

Raffaele Giancarlo, B. Racz, Adam L. Buchsbaum

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.06.056

zbMATH Keywords

communication complexityextremal graph theoryspace lower boundsgraph algorithms for data streams

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cites Work

• An information statistics approach to data stream and communication complexity
• On randomized one-round communication complexity
• On finding common neighborhoods in massive graphs.
• New asymptotics for bipartite Turán numbers
• Authoritative sources in a hyperlinked environment
• Communication Complexity
• Automata, Languages and Programming
• Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: New results for finding common neighborhoods in massive graphs in the data stream model