1 citations · 1 across the 4 of their papers we have counts for
Showing 2026Show all
2 papers · 1 filter
cs.DS2026
A Near-Optimal Parallel Algorithm for Finding Matroid Bases
Sanjeev Khanna, Aaron Putterman, Junkai Song
We settle the classic question of the parallel complexity of computing a matroid basis, as first posed in the seminal work of Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988). Our…
cs.DS2026
A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
Julia Chuzhoy, Sanjeev Khanna, Junkai Song
In the fully dynamic maximal matching problem, the goal is to maintain a maximal matching in a graph undergoing an online sequence of edge insertions and deletions. The problem has…