Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
From MaRDI portal
Publication:3452791
DOI10.1007/978-3-662-48350-3_23zbMath1466.68086arXiv1505.02019OpenAlexW1617753329MaRDI QIDQ3452791
Chris Schwiegelshohn, Marc Bury
Publication date: 19 November 2015
Published in: Algorithms - ESA 2015 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1505.02019
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (10)
Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Unnamed Item ⋮ Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Structural results on matching estimation with applications to streaming ⋮ Unnamed Item ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ On Approximating Matrix Norms in Data Streams ⋮ Almost-smooth histograms and sliding-window graph algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parallel approximation algorithms for maximum weighted matching in general graphs
- Pseudorandom generators for space-bounded computation
- Weighted matching in the semi-streaming model
- On graph problems in a semi-streaming model
- Dynamic Graphs in the Sliding-Window Model
- Spectral Sparsification in Dynamic Graph Streams
- Improved Bounds for Online Preemptive Matching
- Maximum Matching in Semi-streaming with Few Passes
- Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
- Maximum Matching in Turnstile Streams
- Exponential Separation of Quantum and Classical One-Way Communication Complexity
- Graph Sparsification in the Semi-streaming Model
- Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Numerical linear algebra in the streaming model
- Turnstile streaming algorithms might as well be linear sketches
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- The Factorization of Linear Graphs
This page was built for publication: Sublinear Estimation of Weighted Matchings in Dynamic Data Streams