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

DOI10.1007/S10878-022-00929-ZOpenAlexW3109520868MaRDI QIDQ2106871FDOQ2106871

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

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

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)

Cites Work

• The space complexity of approximating the frequency moments
• Random sampling with a reservoir
• Decomposition of Finite Graphs Into Forests
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Improved Distributed Approximate Matching
• Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• 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
• Structural results on matching estimation with applications to streaming
• Planar Matching in Streams Revisited
• The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
• Title not available (Why is that?)
• Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Cited In (2)

• Dynamic graph stream algorithms in \(o(n)\) space
• A Hall-type theorem with algorithmic consequences in planar graphs

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)