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.