Tight Bounds for Graph Problems in Insertion Streams

DOI10.4230/LIPIcs.APPROX-RANDOM.2015.435zbMath1375.68062OpenAlexW2296544654MaRDI QIDQ5351915

David P. Woodruff, Xiaoming Sun

Publication date: 31 August 2017

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5316/pdf/26.pdf/

zbMATH Keywords

graphscommunication complexitydata streamsspace complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items

Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ A one pass streaming algorithm for finding Euler tours ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Dynamic graph stream algorithms in \(o(n)\) space