An estimator for matching size in low arboricity graphs with two applications
From MaRDI portal
Publication:2106871
DOI10.1007/s10878-022-00929-zOpenAlexW3109520868MaRDI QIDQ2106871
Publication date: 29 November 2022
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2011.11706
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (2)
A Hall-type theorem with algorithmic consequences in planar graphs ⋮ Dynamic graph stream algorithms in \(o(n)\) space
Cites Work
- Unnamed Item
- The space complexity of approximating the frequency moments
- Structural results on matching estimation with applications to streaming
- Improved Distributed Approximate Matching
- Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs
- Random sampling with a reservoir
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Planar Matching in Streams Revisited
- The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
- Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- Parameterized Streaming: Maximal Matching and Vertex Cover
- Approximating matching size from random streams
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Decomposition of Finite Graphs Into Forests
This page was built for publication: An estimator for matching size in low arboricity graphs with two applications
