3 papers
cs.DS2026
Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications
Keerti Choudhary, Amit Kumar, Lakshay Saggi
Sensitivity oracles preprocess a graph so that queries can be answered after any edge insertions and deletions, without recomputing from scratch. For structural optimization pr…
cs.DS2025
Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
Mridul Ahi, Keerti Choudhary, Shlok Pande +2
Given a digraph with a designated source , sink , and an -max-flow of value , we present constructions for max-flow and min-cut sensitivity oracles, an…
cs.DS2025
Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
Keerti Choudhary, Amit Kumar, Lakshay Saggi
We study the 2-Disjoint Shortest Paths (2-DSP) problem: given a directed weighted graph and two terminal pairs and , decide whether there exist vertex-disjoi…