Dynamic matching with better-than-2 approximation in polylogarithmic update time

DOI10.1137/1.9781611977554.CH5MaRDI QIDQ6538530FDOQ6538530

Authors: Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David Wajc 

Publication date: 14 May 2024

Recommendations

• 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 maximal matching in \(O(\log n)\) update time

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

This page was built for publication: Dynamic matching with better-than-2 approximation in polylogarithmic update time

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