Reproduce “Deterministic Dynamic Maximal Matching in Sublinear Update Time” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
The authors maintain a maximal matching as graph edges are inserted or deleted. They use an edge-degree constrained subgraph (EDCS) to keep high-degree vertices matched, reducing the work needed on the remaining vertices. The deterministic algorithm has tilde O(n^{8/9}) amortized update time; a randomized version achieves tilde O(n^{3/4}) with high probability against an adaptive adversary, not per-update worst-case bounds.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.