scientific article; zbMATH DE number 7122325

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.

zbMATH Keywords

matchingplanar graphsdata streamsarboricity

Mathematics Subject Classification ID

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: