2 citations · 3 across the 12 of their papers we have counts for
4 papers · 1 filter
Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
Yaowei Long, Seth Pettie, Thatchaphol Saranurak
We consider the problem of assigning short labels to the vertices and edges of a graph so that given any query with , we can determine whether…
Unbreakable Decomposition in Close-to-Linear Time
Aditya Anand, Euiwoong Lee, Jason Li +2
Unbreakable decomposition, introduced by Cygan et al. (SICOMP'19) and Cygan et al. (TALG'20), has proven to be one of the most powerful tools for parameterized graph cut problems i…
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…
Dynamic Deterministic Constant-Approximate Distance Oracles with Worst-Case Update Time
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak
We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph with vertices undergoing both edge insertions and deletions, and an a…