2 papers
cs.DS2024
Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
Aditya Anand, Thatchaphol Saranurak, Yunfan Wang
We give the first deterministic algorithm that makes sub-quadratic queries to find the global min-cut of a simple graph in the cut query model. Given an -vertex graph , our a…
cs.DS2024
Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity
Yaowei Long, Yunfan Wang
We study the \emph{sensitivity oracles problem for subgraph connectivity} in the \emph{decremental} and \emph{fully dynamic} settings. In the fully dynamic setting, we preprocess a…