Sublinear Estimation of Weighted Matchings in Dynamic Data Streams

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

Mathematics Subject Classification ID

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