Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams

DOI10.1137/1.9781611974331.ch92zbMath1409.68341arXiv1505.01731OpenAlexW4246633356MaRDI QIDQ4575674

Sofya Vorotnikova, Rajesh Chitnis, Andrew McGregor, Hossein Esfandiari, Morteza Monemizadeh, Graham Cormode, Mohammad Taghi Hajiaghayi

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://arxiv.org/abs/1505.01731

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items (28)

Multistage vertex cover ⋮ Streaming deletion problems parameterized by vertex cover ⋮ Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Unnamed Item ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Stochastic packing integer programs with few queries ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Almost optimal query algorithm for hitting set using a subset query ⋮ Space limited graph algorithms on big data ⋮ Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Matroid-constrained vertex cover ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ Space limited linear-time graph algorithms on big data ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ Brief Announcement: MapReduce Algorithms for Massive Trees ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Structural results on matching estimation with applications to streaming ⋮ Fixed parameter tractability of graph deletion problems over data streams ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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 ⋮ Almost-smooth histograms and sliding-window graph algorithms ⋮ Linear-time parameterized algorithms with limited local resources ⋮ An estimator for matching size in low arboricity graphs with two applications

This page was built for publication: Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams