Sanjeev Khanna

collaborators

2 papers

cs.DS2026

An $n^{2 + o (1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths

Sanjeev Khanna, Junkai Song

We present a randomized algorithm for the single-source shortest paths (SSSP) problem on directed graphs with arbitrary real-valued edge weights that runs in $n^{2 + o (1)}$ time with…

cs.DS2024

Maximum Bipartite Matching in $n^{2 + o (1)}$ Time via a Combinatorial Algorithm

Julia Chuzhoy, Sanjeev Khanna

Maximum bipartite matching (MBM) is a fundamental problem in combinatorial optimization with a long and rich history. A classic result of Hopcroft and Karp (1973) provides an $O(m…

An n2+o(1) Time Algorithm for Single-Source Negative Weight Shortest Paths

Maximum Bipartite Matching in n2+o(1) Time via a Combinatorial Algorithm

An $n^{2 + o (1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths

Maximum Bipartite Matching in $n^{2 + o (1)}$ Time via a Combinatorial Algorithm