
Decremental AllPairs Shortest Paths in Deterministic NearLinear Time
We study the decremental AllPairs Shortest Paths (APSP) problem in undi...
read it

Towards Better Approximation of Graph Crossing Number
Graph Crossing Number is a fundamental problem with various applications...
read it

Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition
In the decremental singlesource shortest paths (SSSP) problem, the inpu...
read it

On Packing LowDiameter Spanning Trees
Edge connectivity of a graph is one of the most fundamental graphtheore...
read it

Pinning Down the Strong Wilber 1 Bound for Binary Search Trees
The famous dynamic optimality conjecture of Sleator and Tarjan from 1985...
read it

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
We consider the classical Minimum Balanced Cut problem: given a graph G,...
read it

A New Algorithm for Decremental SingleSource Shortest Paths with Applications to VertexCapacitated Flow and Cut Problems
We study the vertexdecremental SingleSource Shortest Paths (SSSP) prob...
read it

Large Minors in Expanders
In this paper we study expander graphs and their minors. Specifically, w...
read it

Towards Tight(er) Bounds for the Excluded Grid Theorem
We study the Excluded Grid Theorem, a fundamental structural result in g...
read it

Improved Approximation for NodeDisjoint Paths in Grids with Sources on the Boundary
We study the classical NodeDisjoint Paths (NDP) problem: given an undir...
read it

Almost Polynomial Hardness of NodeDisjoint Paths in Grids
In the classical NodeDisjoint Paths (NDP) problem, we are given an nve...
read it
Julia Chuzhoy
is this you? claim profile