Lakshay Saggi

collaborators

Showing cs.DSShow all

4 papers · 1 filter

cs.DS2026

Smallest Multiplicative Stretch for an $α$ -APASP Below $O (n^{ω})$ Runtime

Lakshay Saggi, Ariel Sapir

Dor, Halperin and Zwick [FOCS'96; SICOMP'00] showed that $(2 - ε)$ -APASP is at least as hard as BMM for every fixed $0 < ε < 1$ . Zwick [FOCS'98; JACM'02] gave a $2$ -A…

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 $f$ 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 $G = (V, E)$ with a designated source $s$ , sink $t$ , and an $(s, t)$ -max-flow of value $λ$ , we present constructions for max-flow and min-cut sensitivity oracles, an…