1 citations · 1 across the 10 of their papers we have counts for
4 papers · 1 filter
Matching Composition and Efficient Weight Reduction in Dynamic Matching
Aaron Bernstein, Jiale Chen, Aditi Dudeja +3
We consider the foundational problem of maintaining a -approximate maximum weight matching (MWM) in an -node dynamic graph undergoing edge insertions and deleti…
Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
Aditi Dudeja, Rashmika Goswami, Michael Saks
Vizing's theorem states that any graph of maximum degree can be properly edge colored with at most colors. In the online setting, it has been a matter of interest to find…
Evolution of locally dependent random graphs
Joshua Brody, Pat Devlin, Aditi Dudeja +1
In this paper we study -dependent random graphs -- introduced by Brody and Sanchez -- which are the family of random graph distributions where each edge is present with probabil…
A Note on Rounding Matchings in General Graphs
Aditi Dudeja
In this note, we revisit the rounding algorithm of Wajc. Wajc gave a fully-adaptive randomized algorithm that rounds a dynamic fractional matching in an unweighted bipartite graph…