Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach

DOI10.1137/1.9781611974331.ch51zbMath1410.68305OpenAlexW4250173201MaRDI QIDQ4575629

Shay Solomon, David Peleg

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch51

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Related Items (11)

Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Simple Distributed Spanners in Dense Congest Networks ⋮ A simple greedy algorithm for dynamic graph orientation ⋮ Unnamed Item ⋮ Approximating dynamic weighted vertex cover with soft capacities ⋮ Improved algorithm for dynamic b-Matching ⋮ Improved Dynamic Graph Coloring

This page was built for publication: Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach