Faster fully dynamic matchings with small approximation ratios
DOI10.1137/1.9781611974331.CH50zbMATH Open1409.68203OpenAlexW4235789583MaRDI QIDQ4575628FDOQ4575628
Authors: Aaron Bernstein, Clifford Stein 
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.ch50
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (27)
- A simple greedy algorithm for dynamic graph orientation
- Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
- Fully dynamic matching in bipartite graphs
- Deterministic fully dynamic data structures for vertex cover and matching
- Fully dynamic maximal matching in \(O(\log n)\) update time (corrected version)
- Towards a unified theory of sparsification for matching problems
- Maximum matching on trees in the online preemptive and the incremental graph models
- Faster dynamic matchings and vertex connectivity
- Dominating sets and connected dominating sets in dynamic graphs
- Title not available (Why is that?)
- Dynamic Matching Algorithms in Practice
- \((1 + \varepsilon)\)-approximate incremental matching in constant deterministic amortized time
- Deterministic dynamic matching in worst-case update time
- Local algorithms for bounded degree sparsifiers in sparse graphs
- Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
- Distributed algorithms for matching in hypergraphs
- On regularity lemma and barriers in streaming and dynamic matching
- Sublinear algorithms for \((1.5+\epsilon)\)-approximate matching
- Sublinear time algorithms and complexity of approximate maximum matching
- A simple greedy algorithm for dynamic graph orientation
- Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
- Improved dynamic graph coloring
- Round compression for parallel matching algorithms
- Improved algorithm for dynamic \(b\)-matching
- Lazy or eager dynamic matching may not be fast
- Deterministic dynamic matching in \(O(1)\) update time
- Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach
This page was built for publication: Faster fully dynamic matchings with small approximation ratios
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575628)
