Sanjeev Khanna

most citedPerfect Matchings in Õ(n^{1.5}) Time in Regular Bipartite Graphs

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

collaborators

2 papers

cs.DS2009★ 4 cited

Perfect Matchings in Õ(n^{1.5}) Time in Regular Bipartite Graphs

Ashish Goel, Michael Kapralov, Sanjeev Khanna

We consider the well-studied problem of finding a perfect matching in $d$ -regular bipartite graphs with $2 n$ vertices and $m = n d$ edges. While the best-known algorithm for general…

cs.DS2008★ 1 cited

An $O (k^{3} l o g n)$ -Approximation Algorithm for Vertex-Connectivity Survivable Network Design

Julia Chuzhoy, Sanjeev Khanna

In the Survivable Network Design problem (SNDP), we are given an undirected graph $G (V, E)$ with costs on edges, along with a connectivity requirement $r (u, v)$ for each pair $u, v$ o…

Perfect Matchings in Õ(n^{1.5}) Time in Regular Bipartite Graphs

An O(k3logn)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design

An $O (k^{3} l o g n)$ -Approximation Algorithm for Vertex-Connectivity Survivable Network Design