An estimator for matching size in low arboricity graphs with two applications
type: Item
instance of: scholarly article
title: An estimator for matching size in low arboricity graphs with two applications
author: Hossein Jowhari
published in: Journal of Combinatorial Optimization
publication date: 2022-11-29T00:00:00Z
full work available at URL: https://arxiv.org/abs/2011.11706
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7625357
zbMATH Keywords: maximum matching
zbMATH Keywords: approximation algorithms
zbMATH Keywords: data stream algorithms
MaRDI profile type: Publication
OpenAlex ID: W3109520868
cites work: The space complexity of approximating the frequency moments
cites work: Structural results on matching estimation with applications to streaming
cites work: Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
cites work: Parameterized Streaming: Maximal Matching and Vertex Cover
cites work: Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs
cites work: The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
cites work: Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
cites work: Approximating matching size from random streams
cites work: Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
cites work: Improved Distributed Approximate Matching
cites work: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
cites work: Planar Matching in Streams Revisited
cites work: Q5240429
cites work: Decomposition of Finite Graphs Into Forests
cites work: Random sampling with a reservoir
DOI: 10.1007/S10878-022-00929-Z
description: scientific article; zbMATH DE number 7625357