Dynamic graph stream algorithms in o(n) space

DOI10.4230/LIPICS.ICALP.2016.18zbMATH Open1388.68231arXiv1605.00089MaRDI QIDQ4598151FDOQ4598151

Pan Peng, Zengfeng Huang

Publication date: 19 December 2017

Full work available at URL: https://arxiv.org/abs/1605.00089

Recommendations

• Dynamic graph stream algorithms in \(o(n)\) space
• Tight bounds for graph problems in insertion streams
• Graph distances in the streaming model: the value of space
• Estimating graph parameters from random order streams
• scientific article; zbMATH DE number 7053292

zbMATH Keywords

minimum spanning treesketchingproperty testingdynamic graph streams

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cited In (9)

• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Streamed Graph Drawing and the File Maintenance Problem
• Labeled graph sketches: keeping up with real-time graph streams
• Dynamic graph stream algorithms in \(o(n)\) space
• Space lower bounds for graph stream problems
• Average Sensitivity of Graph Algorithms
• Graph spanners in the streaming model: An experimental study
• Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond

This page was built for publication: Dynamic graph stream algorithms in \(o(n)\) space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598151)