Matching Composition and Efficient Weight Reduction in Dynamic Matching

Aaron Bernstein, Jiale Chen, Aditi Dudeja +3

We consider the foundational problem of maintaining a $(1-\epsilon )$-approximate maximum weight matching (MWM) in an $n$-node dynamic graph undergoing edge insertions and deleti…