Improved algorithm for dynamic b-matching

DOI10.4230/LIPICS.ESA.2017.15MaRDI QIDQ5111701zbMATH OpenOpenAlexFDO

Authors Sayan Bhattacharya, Manoj Gupta, Divyarthi Mohan

Publication date 27 May 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/7844/pdf/LIPIcs-ESA-2017-15.pdf/

zbMATH Keywords

dynamic data structuresgraph algorithms

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Fully dynamic maximal matching in O( n) update time
• New deterministic approximation algorithms for fully dynamic matching
• Fully dynamic matching in bipartite graphs
• Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
• Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time

Cites work

• Design of dynamic algorithms via primal-dual method
• Deterministic fully dynamic data structures for vertex cover and matching
• Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach
• Faster fully dynamic matchings with small approximation ratios
• Fully dynamic matching in bipartite graphs
• Fully Dynamic Maximal Matching in O (log n) Update Time
• Maintaining a large matching and a small vertex cover
• New deterministic approximation algorithms for fully dynamic matching
• Online and dynamic algorithms for set cover

Cited in

(2)

• Lazy or eager dynamic matching may not be fast
• Dynamic Matching Algorithms in Practice

This page was built for publication: Improved algorithm for dynamic \(b\)-matching

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