The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
From MaRDI portal
(Redirected from Publication:5111716)
Abstract: Estimating the size of the maximum matching is a canonical problem in graph algorithms, and one that has attracted extensive study over a range of different computational models. We present improved streaming algorithms for approximating the size of maximum matching with sparse (bounded arboricity) graphs. * Insert-Only Streams: We present a one-pass algorithm that takes O(c log^2 n) space and approximates the size of the maximum matching in graphs with arboricity c within a factor of O(c). This improves significantly on the state-of-the-art O~(cn^{2/3})-space streaming algorithms. * Dynamic Streams: Given a dynamic graph stream (i.e., inserts and deletes) of edges of an underlying c-bounded arboricity graph, we present a one-pass algorithm that uses space O~(c^{10/3}n^{2/3}) and returns an O(c)-estimator for the size of the maximum matching. This algorithm improves the state-of-the-art O~(cn^{4/5})-space algorithms, where the O~(.) notation hides logarithmic in dependencies. In contrast to the previous works, our results take more advantage of the streaming access to the input and characterize the matching size based on the ordering of the edges in the stream in addition to the degree distributions and structural properties of the sparse graphs.
Recommendations
- Structural results on matching estimation with applications to streaming
- A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs
- On estimating maximum matching size in graph streams
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- Streaming algorithms for estimating the matching size in planar graphs and beyond
Cites work
- A \((2 + \epsilon)\)-approximation for maximum weight matching in the semi-streaming model
- AdWords and generalized online matching
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Approximating matching size from random streams
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Better bounds for matchings in the streaming model
- Bipartite matching in the semi-streaming model
- Decomposition of Finite Graphs Into Forests
- Edge-Disjoint Spanning Trees of Finite Graphs
- scientific article; zbMATH DE number 48303 (Why is no real title available?)
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- Improved approximation guarantees for weighted matching in the semi-streaming model
- Improved streaming algorithms for weighted matching, via unweighted matching
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Linear-time approximation for maximum weight matching
- Lower bound of the Hadwiger number of graphs by their average degree
- Matching for Graphs of Bounded Degree
- Matching theory
- Maximum matching in semi-streaming with few passes
- Maximum matchings in dynamic graph streams and the simultaneous communication model
- On estimating maximum matching size in graph streams
- On graph problems in a semi-streaming model
- On Unifying the Space of ℓ0-Sampling Algorithms
- Planar matching in streams revisited
- Spectral sparsification in dynamic graph streams
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- Sublinear estimation of weighted matchings in dynamic data streams
- The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
- Tight bounds on the round complexity of the distributed maximum coverage problem
- Weighted matching in the semi-streaming model
Cited in
(22)- Structural results on matching estimation with applications to streaming
- Fixed parameter tractability of graph deletion problems over data streams
- Almost-smooth histograms and sliding-window graph algorithms
- An estimator for matching size in low arboricity graphs with two applications
- Sublinear estimation of weighted matchings in dynamic data streams
- On estimating maximum matching size in graph streams
- Streaming algorithms for estimating the matching size in planar graphs and beyond
- The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
- A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- Approximating matching size from random streams
- scientific article; zbMATH DE number 7758318 (Why is no real title available?)
- Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model
- Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
- Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
- (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
- Improved bounds for matching in random-order streams
- Improved bounds for matching in random-order streams
- Weighted matching in the random-order streaming and robust communication models
- Matchings in low-arboricity graphs in the dynamic graph stream model
- Range counting oracles for geometric problems
- Sublinear space graph algorithms in the continual release model
This page was built for publication: The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111716)
