32 citations · 59 across the 26 of their papers we have counts for
36 papers
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…
Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
Julia Chuzhoy, Merav Parter
A -spanner of an undirected -vertex graph is a sparse subgraph of that preserves all pairwise distances between its vertices to within multiplicative factor ,…
Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
Julia Chuzhoy, Ron Mosenzon, Ohad Trabelsi
We study the directed global minimum vertex-cut problem: given a directed vertex-weighted graph , compute a vertex-cut in of minimum value, which is defined to be…
Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
Julia Chuzhoy, Ohad Trabelsi
We consider the Global Minimum Vertex-Cut problem: given an undirected vertex-weighted graph , compute a minimum-weight subset of its vertices whose removal disconnects . The…
Maximum Bipartite Matching in Time via a Combinatorial Algorithm
Julia Chuzhoy, Sanjeev Khanna
Maximum bipartite matching (MBM) is a fundamental problem in combinatorial optimization with a long and rich history. A classic result of Hopcroft and Karp (1973) provides an $O(m…
A Faster Combinatorial Algorithm for Maximum Bipartite Matching
Julia Chuzhoy, Sanjeev Khanna
The maximum bipartite matching problem is among the most fundamental and well-studied problems in combinatorial optimization. A beautiful and celebrated combinatorial algorithm of…