Deterministic dynamic matching in \(O(1)\) update time
DOI10.1007/s00453-019-00630-4zbMath1435.68226OpenAlexW2974991453WikidataQ127181388 ScholiaQ127181388MaRDI QIDQ2300734
Deeparnab Chakrabarty, Sayan Bhattacharya, Monika R. Henzinger
Publication date: 28 February 2020
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-019-00630-4
Analysis of algorithms (68W40) 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) Data structures (68P05) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for fully dynamic connectivity problems in graphs
- Shortest augmenting paths for online matchings on trees
- Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
- Maintaining a large matching and a small vertex cover
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Design of Dynamic Algorithms via Primal-Dual Method
- Local-on-Average Distributed Tasks
- Faster Fully Dynamic Matchings with Small Approximation Ratios
- Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time
- Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
- Online and dynamic algorithms for set cover
- Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time
- New deterministic approximation algorithms for fully dynamic matching
- Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
- Fully Dynamic Maximal Matching in O (log n) Update Time
This page was built for publication: Deterministic dynamic matching in \(O(1)\) update time
