scientific article; zbMATH DE number 7122325
From MaRDI portal
Publication:5240429
DOI10.4230/OASIcs.SOSA.2018.14zbMath1433.68622MaRDI QIDQ5240429
Andrew McGregor, Sofya Vorotnikova
Publication date: 25 October 2019
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)
Related Items (8)
Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ Unnamed Item ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Structural results on matching estimation with applications to streaming ⋮ Fixed parameter tractability of graph deletion problems over data streams ⋮ Almost-smooth histograms and sliding-window graph algorithms ⋮ An estimator for matching size in low arboricity graphs with two applications
Cites Work
- Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
- 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
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- Maximum matching and a polyhedron with 0,1-vertices
This page was built for publication: