Fully Dynamic Matching: -Approximation in Polylog Update Time
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani · Society for Industrial and Applied Mathematics eBooks · 2024
We study maximum matchings in fully dynamic graphs, which are graphs that undergo both edge insertions and deletions. Our focus is on algorithms that estimate the size of maximum matching after each update while spending a small time.