Julia Chuzhoy

activity

20092026

most citedA Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

32 citations · 59 across the 26 of their papers we have counts for

collaborators

Showing 2016Show all

4 papers · 1 filter

cs.DS2016

New Hardness Results for Routing on Disjoint Paths

Julia Chuzhoy, David H. K. Kim, Rachit Nimavat

In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected $n$ -vertex graph $G$ , and a collection $M = {(s_{1}, t_{1}), \dots, (s_{k}, t_{k})}$ of pairs…

cs.DS2016

On Approximating Maximum Independent Set of Rectangles

Julia Chuzhoy, Alina Ene

We study the Maximum Independent Set of Rectangles (MISR) problem: given a set of $n$ axis-parallel rectangles, find a largest-cardinality subset of the rectangles, such that no tw…

cs.DS2016★ 7 cited

Improved Approximation for Node-Disjoint Paths in Planar Graphs

Julia Chuzhoy, David H. K. Kim, Shi Li

We study the classical Node-Disjoint Paths (NDP) problem: given an $n$ -vertex graph $G$ and a collection $M = {(s_{1}, t_{1}), \dots, (s_{k}, t_{k})}$ of pairs of vertices of $G$ called deman…

cs.DM2016

Improved Bounds for the Excluded Grid Theorem

Julia Chuzhoy

We study the Excluded Grid Theorem of Robertson and Seymour. This is a fundamental result in graph theory, that states that there is some function $f : Z^{+} \to Z^{+}$ , such tha…