An estimator for matching size in low arboricity graphs with two applications

DOI10.1007/S10878-022-00929-ZMaRDI QIDQ2106871zbMATH OpenOpenAlexFDO

Authors Hossein Jowhari

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

zbMATH Keywords

approximation algorithmsmaximum matchingdata stream algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Streaming algorithms for estimating the matching size in planar graphs and beyond
• Planar matching in streams revisited
• Structural results on matching estimation with applications to streaming
• A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs

Cites work

• A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs
• Approximating matching size from random streams
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Decomposition of Finite Graphs Into Forests
• Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs
• Improved Distributed Approximate Matching
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Planar matching in streams revisited
• Random sampling with a reservoir
• Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Structural results on matching estimation with applications to streaming
• The space complexity of approximating the frequency moments
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs

Cited in

(4)

• Dynamic graph stream algorithms in \(o(n)\) space
• Streaming algorithms for estimating the matching size in planar graphs and beyond
• A Hall-type theorem with algorithmic consequences in planar graphs
• Matchings in low-arboricity graphs in the dynamic graph stream model

This page was built for publication: An estimator for matching size in low arboricity graphs with two applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2106871)