Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model

DOI10.1137/1.9781611974331.ch93zbMath1409.68337OpenAlexW4241765972MaRDI QIDQ4575676

Sepelir Assadi, Yang Li, Sanjeev Khanna, Grigory Yaroslavtsev

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch93

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Network protocols (68M12) Online algorithms; streaming algorithms (68W27)

Related Items (15)

Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Deterministic dynamic matching in worst-case update time ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ High Probability Frequency Moment Sketches ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Structural results on matching estimation with applications to streaming ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Querying a Matrix Through Matrix-Vector Products. ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ Optimality of linear sketching under modular updates ⋮ Better streaming algorithms for the maximum coverage problem ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs

This page was built for publication: Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model