Optimal lower bounds for matching and vertex cover in dynamic graph streams
From MaRDI portal
Publication:5092481
DOI10.4230/LIPIcs.CCC.2020.30OpenAlexW3035186030MaRDI QIDQ5092481
Christian Konrad, Jacques Dark
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/2005.11116
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Streaming algorithms for independent sets in sparse hypergraphs
- On data structures and asymmetric communication complexity
- Approximating the Caro-Wei bound for independent sets in graph streams
- A second look at counting triangles in graph streams (corrected)
- Streaming and Communication Complexity of Clique Approximation
- Counting Arbitrary Subgraphs in Data Streams
- Maximum Matching in Semi-streaming with Few Passes
- Maximum Matching in Turnstile Streams
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
- A (2+ϵ)-Approximation for Maximum Weight Matching in the Semi-streaming Model
- Approximating Semi-matchings in Streaming and in Two-Party Communication
- Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
- A simple augmentation method for matchings with applications to streaming algorithms
- Optimality of linear sketching under modular updates
- Separations and equivalences between turnstile streaming and linear sketching
- Approximate Maximum Matching in Random Streams
- Fast and Space Efficient Spectral Sparsification in Dynamic Streams
- Sublinear Algorithms for (Δ + 1) Vertex Coloring
- Turnstile streaming algorithms might as well be linear sketches
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Approximating matching size from random streams
This page was built for publication: Optimal lower bounds for matching and vertex cover in dynamic graph streams
