Deterministic rounding of dynamic fractional matchings

DOI10.4230/LIPICS.ICALP.2021.27MaRDI QIDQ7241124zbMATH OpenFDO

Authors Sayan Bhattacharya, Peter Kiss

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.27

zbMATH Keywords

data structuresdynamic algorithmsmatching

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A deamortization approach for dynamic spanner and dynamic maximal matching
• A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond
• Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
• Deterministic fully dynamic data structures for vertex cover and matching
• Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time
• Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach
• Dynamic Edge Coloring with Improved Approximation
• Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
• Edge-Disjoint Spanning Trees of Finite Graphs
• Faster dynamic matchings and vertex connectivity
• Faster fully dynamic matchings with small approximation ratios
• Fully dynamic (1+ e)-approximate matchings
• Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
• Fully dynamic matching in bipartite graphs
• Fully Dynamic Matching: Beating 2-Approximation in Δ^ϵ Update Time
• Fully dynamic maximal independent set with polylogarithmic update time
• Higher lower bounds from the 3SUM conjecture
• scientific article; zbMATH DE number 1263228 (Why is no real title available?)
• scientific article; zbMATH DE number 7788470 (Why is no real title available?)
• Maintaining a large matching and a small vertex cover
• Maintaining approximate maximum matching in an incremental bipartite graph in polylogarithmic update time
• New deterministic approximation algorithms for fully dynamic matching
• Orienting fully dynamic graphs with worst-case time bounds
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Rounding dynamic matchings against an adaptive adversary
• Simple deterministic algorithms for fully dynamic maximal matching
• The cell probe complexity of dynamic range counting
• Towards a unified theory of sparsification for matching problems
• Towards polynomial lower bounds for dynamic problems

This page was built for publication: Deterministic rounding of dynamic fractional matchings

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