Faster fully dynamic matchings with small approximation ratios

DOI10.1137/1.9781611974331.CH50MaRDI QIDQ4575628zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

Recommendations

• Fully dynamic matching in bipartite graphs
• New deterministic approximation algorithms for fully dynamic matching
• Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach

Cited in

(35)

• A simple greedy algorithm for dynamic graph orientation
• Distributed algorithms for matching in hypergraphs
• Lazy or eager dynamic matching may not be fast
• Deterministic dynamic matching in \(O(1)\) update time
• Maximum matching on trees in the online preemptive and the incremental graph models
• Faster dynamic matchings and vertex connectivity
• Fully dynamic matching in bipartite graphs
• Deterministic fully dynamic data structures for vertex cover and matching
• Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach
• scientific article; zbMATH DE number 6866348 (Why is no real title available?)
• Fully dynamic maximal matching in O( n) update time (corrected version)
• 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
• Improved dynamic graph coloring
• Dominating sets and connected dominating sets in dynamic graphs
• Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
• Improved algorithm for dynamic b-matching
• Round compression for parallel matching algorithms
• A simple greedy algorithm for dynamic graph orientation
• (1 + )-approximate incremental matching in constant deterministic amortized time
• Dynamic Matching Algorithms in Practice
• Deterministic dynamic matching in worst-case update time
• On regularity lemma and barriers in streaming and dynamic matching
• Sublinear algorithms for (1.5+)-approximate matching
• Sublinear time algorithms and complexity of approximate maximum matching
• Towards a unified theory of sparsification for matching problems
• Weighted matching in the random-order streaming and robust communication models
• Maximum weight b-matchings in random-order streams
• Dynamic matching with better-than-2 approximation in polylogarithmic update time
• A generalized matching reconfiguration problem
• Beating two-thirds for random-order streaming matching
• Deterministic rounding of dynamic fractional matchings
• Locally computing edge orientations
• Tree-packing revisited: faster fully dynamic min-cut and arboricity

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)