Dynamic (1 + )-approximate matchings: a density-sensitive approach

DOI10.1137/1.9781611974331.CH51MaRDI QIDQ4575629zbMATH OpenOpenAlexFDO

Authors 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

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Faster fully dynamic matchings with small approximation ratios
• New deterministic approximation algorithms for fully dynamic matching
• Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
• Fully dynamic matching in bipartite graphs

Cited in

(18)

• A simple greedy algorithm for dynamic graph orientation
• Approximating dynamic weighted vertex cover with soft capacities
• Deterministic dynamic matching in \(O(1)\) update time
• Simple distributed spanners in dense congest networks
• Faster fully dynamic matchings with small approximation ratios
• Local algorithms for bounded degree sparsifiers in sparse graphs
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
• An \(o(1)\)-approximation algorithm for dynamic weighted vertex cover with soft capacity
• Improved dynamic graph coloring
• Improved algorithm for dynamic b-matching
• A simple greedy algorithm for dynamic graph orientation
• New deterministic approximation algorithms for fully dynamic matching
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Sparsity-parameterised dynamic edge colouring
• Dynamic matching with better-than-2 approximation in polylogarithmic update time
• Deterministic rounding of dynamic fractional matchings
• Tree-packing revisited: faster fully dynamic min-cut and arboricity

This page was built for publication: Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach

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