3 papers
cs.DS2026
An 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 time with…
cs.DS2024
Maximum Bipartite Matching in 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…
cs.DS2023
A Faster Combinatorial Algorithm for Maximum Bipartite Matching
Julia Chuzhoy, Sanjeev Khanna
The maximum bipartite matching problem is among the most fundamental and well-studied problems in combinatorial optimization. A beautiful and celebrated combinatorial algorithm of…