David H. K. Kim

activity

20162018

most citedImproved Approximation for Node-Disjoint Paths in Planar Graphs

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

collaborators

4 papers

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…

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…