Dynamic graph stream algorithms in \(o(n)\) space

DOI10.1007/s00453-018-0520-8zbMath1422.68322WikidataQ64109576 ScholiaQ64109576MaRDI QIDQ1741857

Pan Peng, Zengfeng Huang

Publication date: 7 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0520-8

zbMATH Keywords

minimum spanning tree; property testing; dynamic graph streams; graph sketching

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

68W20: Randomized algorithms

68W27: Online algorithms; streaming algorithms