7 papers
Reachability in Directed Acyclic Graphs with Near-Linear Cut Queries
Sanjeev Khanna, Aaron Putterman, Junkai Song
In the cut-query model, an algorithm is given access to a graph \emph{only} via cut queries. This model has seen significant attention in the undirected graph setting,…
A Near-Optimal Parallel Algorithm for Finding Matroid Bases
Sanjeev Khanna, Aaron Putterman, Junkai Song
We settle the classic question of the parallel complexity of computing a matroid basis, as first posed in the seminal work of Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988). Our…
An Round Parallel Algorithm for Matroid Bases
Sanjeev Khanna, Aaron Putterman, Junkai Song
We study the parallel (adaptive) complexity of the classic problem of finding a basis in an -element matroid, given access via an \emph{independence oracle}. In this model, the…
A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
Julia Chuzhoy, Sanjeev Khanna, Junkai Song
In the fully dynamic maximal matching problem, the goal is to maintain a maximal matching in a graph undergoing an online sequence of edge insertions and deletions. The problem has…
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…
Optimal Parallel Basis Finding in Graphic and Related Matroids
Sanjeev Khanna, Aaron Putterman, Junkai Song
We study the parallel complexity of finding a basis of a graphic matroid under independence-oracle access. Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988) initiated the study of…