Structural results on matching estimation with applications to streaming

DOI10.1007/s00453-018-0449-yzbMath1412.68163OpenAlexW2804511772MaRDI QIDQ1755797

Chris Schwiegelshohn, Elena Grigorescu, Samson Zhou, Andrew McGregor, Marc Bury, Morteza Monemizadeh, Sofya Vorotnikova

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://zenodo.org/record/4586935

zbMATH Keywords

estimationmatchinggraph streaming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (6)

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 ⋮ A Hall-type theorem with algorithmic consequences in planar graphs ⋮ Unnamed Item ⋮ Fixed parameter tractability of graph deletion problems over data streams ⋮ An estimator for matching size in low arboricity graphs with two applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel approximation algorithms for maximum weighted matching in general graphs
• Weighted matching in the semi-streaming model
• On graph problems in a semi-streaming model
• Frequent Directions: Simple and Deterministic Matrix Sketching
• Dynamic Graphs in the Sliding-Window Model
• Improved Bounds for Online Preemptive Matching
• Buyback Problem - Approximate Matroid Intersection with Cancellation Costs
• Maximum matchings in general graphs through randomization
• Approximate Counting of Cycles in Streams
• Maximum Matching in Semi-streaming with Few Passes
• Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
• Maximum Matching in Turnstile Streams
• Uniform Hashing in Constant Time and Optimal Space
• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• 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
• Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
• On Estimating Maximum Matching Size in Graph Streams
• A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
• Planar Matching in Streams Revisited
• Testable bounded degree graph properties are random order streamable
• The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
• Numerical linear algebra in the streaming model
• On approximating functions of the singular values in a stream
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Approximating matching size from random streams
• On Sketching Matrix Norms and the Top Singular Vector
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Maximum matching and a polyhedron with 0,1-vertices
• Better bounds for matchings in the streaming model
• Eigenvalues of a matrix in the streaming model
• The Factorization of Linear Graphs

This page was built for publication: Structural results on matching estimation with applications to streaming