Fully Dynamic Matching: -Approximation in Polylog Update Time
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
2024Year
7Citations
3Top-tier citations
Abstract
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.
Ask about this paper
Ask your agent about it.
Lune has read the top-tier papers around this one, so every answer names the papers it rests on.
Your agent calls
Lunesearch_papers
Free to start. No credit card required.
Terminal
Install the CLIlune papers get 973e404b-1d2e-42b5-8b97-bf09e2f945b9Cited by top-tier papers3
- Approximating Maximum Matching Requires Almost Quadratic TimeSoheil Behnezhad, Mohammad Roghani, Aviad RubinsteinSTOC 2024 · 2 citations
- Tight Pair Query Lower Bounds for Matching and Earth Mover's DistanceAmir Azarmehr, Soheil Behnezhad, Mohammad Roghani, Aviad RubinsteinFOCS 2025 · 2 citations
- Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update TimeGramoz Goranci, Peter Kiss, Neel Patel, Martin P. Seybold et al.ICML 2025
Related papers
- Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update TimeSayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David WajcSODA 2023 · 11 citations
- New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCSSoheil Behnezhad, Sanjeev KhannaSODA 2022 · 11 citations
- Dynamic Algorithms for Maximum Matching SizeSoheil BehnezhadSODA 2023 · 14 citations
- Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update TimeSayan Bhattacharya, Peter Kiss, Thatchaphol SaranurakFOCS 2023 · 9 citations
- History-Independent Maximal Matchings can be Surprisingly Efficient, and Lead to Better Worst-Case GuaranteesRathish Das, William KuszmaulSODA 2026 · 1 citation
