Better bounds for matchings in the streaming model
From MaRDI portal
Publication:5741830
DOI10.1137/1.9781611973105.121zbMath1423.68343arXiv1206.2269OpenAlexW2952341094MaRDI QIDQ5741830
Publication date: 15 May 2019
Published in: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1206.2269
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)
Related Items (14)
Superlinear lower bounds for multipass graph processing ⋮ Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ Sublinear Algorithms for MAXCUT and Correlation Clustering ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Structural results on matching estimation with applications to streaming ⋮ Unnamed Item ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Unnamed Item ⋮ Depth First Search in the Semi-streaming Model ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
This page was built for publication: Better bounds for matchings in the streaming model
