Rachit Nimavat

activity

20162023

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

4 citations · 4 across the 2 of their papers we have counts for

collaborators

Showing cs.DSShow all

5 papers · 1 filter

cs.DS2023

Graph Theory and its Uses in Graph Algorithms and Beyond

Rachit Nimavat

Graphs are fundamental objects that find widespread applications across computer science and beyond. Graph Theory has yielded deep insights about structural properties of various f…

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★ 4 cited

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…

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…