Improved algorithm for dynamic b-Matching
From MaRDI portal
Publication:5111701
DOI10.4230/LIPIcs.ESA.2017.15zbMath1442.68161OpenAlexW2738466993MaRDI QIDQ5111701
Manoj Gupta, Divyarthi Mohan, Sayan Bhattacharya
Publication date: 27 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7844/pdf/LIPIcs-ESA-2017-15.pdf/
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
- Maintaining a large matching and a small vertex cover
- Fully Dynamic Matching in Bipartite Graphs
- Design of Dynamic Algorithms via Primal-Dual Method
- Faster Fully Dynamic Matchings with Small Approximation Ratios
- Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
- Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
- Online and dynamic algorithms for set cover
- 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
