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

DOI10.1137/1.9781611977554.CH5MaRDI QIDQ6538530zbMATH OpenFDO

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

Publication date 14 May 2024

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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

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)