4 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…