From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction

Aaron Bernstein, Jiale Chen

We study the approximate maximum weight matching (MWM) problem in a fully dynamic graph subject to edge insertions and deletions. We design meta-algorithms that reduce the problem…