Rachit Nimavat

activity

20172019

collaborators

3 papers

cs.DS2019

Large Minors in Expanders

Julia Chuzhoy, Rachit Nimavat

In this paper we study expander graphs and their minors. Specifically, we attempt to answer the following question: what is the largest function $f (n, α, d)$ , such that every $n$ -ver…

cs.DS2018

Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary

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

We study the classical Node-Disjoint Paths (NDP) problem: given an undirected $n$ -vertex graph G, together with a set {(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices, called sou…

cs.DS2017

Almost Polynomial Hardness of Node-Disjoint Paths in Grids

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

In the classical Node-Disjoint Paths (NDP) problem, we are given an $n$ -vertex graph $G = (V, E)$ , and a collection $M = {(s_{1}, t_{1}), \dots, (s_{k}, t_{k})}$ of pairs of its vertices, called…