Simplified and space-optimal semi-streaming \((2+\varepsilon)\)-approximate matching

DOI10.4230/OASICS.SOSA.2019.13zbMATH Open1547.68604MaRDI QIDQ6593568

David Wajc, Mohsen Ghaffari

Publication date: 26 August 2024

zbMATH Keywords

matchingstreamingspace-optimalitysemi-streaming

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) 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 (2)

Improved bounds for matching in random-order streams ⋮ Semi-streaming algorithms for submodular function maximization under \(b\)-matching, matroid, and matchoid constraints

This page was built for publication: Simplified and space-optimal semi-streaming \((2+\varepsilon)\)-approximate matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6593568)