2 citations · 3 across the 12 of their papers we have counts for
14 papers
Hardness of Online Directed Steiner Network
Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi +1
In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands , and asked to find a cheap subgraph connecting each terminal pair. In i…
Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size
Yaowei Long, Seth Pettie, Thatchaphol Saranurak
For an undirected graph and a fault bound , an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pa…
Online Steiner Forest with Recourse
Yaowei Long, Sepideh Mahabadi, Sherry Sarkar +1
In the online Steiner forest problem we are given a graph , and a sequence of terminal pairs which arrive in an online fashion. We are asked to maintain a low-cost s…
Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
Xizhe Li, Yaowei Long, David Pidugu +2
We give an improved connectivity oracle under vertex failures. After a set of vertices fails, our oracle performs an -time update independent of the graph size , a…
A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
Bernhard Haeupler, Yaowei Long, Antti Roeyskoe +1
A fault-tolerant distance labeling scheme assigns a label to each vertex and edge of an undirected weighted graph with vertices so that, for any edge set of size $|F| \…
Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
Yonggang Jiang, Yaowei Long, Thatchaphol Saranurak +1
We give almost-linear-time algorithms for approximating rooted minimum cut and maximum arborescence packing in directed graphs, two problems that are dual to each other [Edm73]. Mo…
Parallel -Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
Bernhard Haeupler, Yonggang Jiang, Yaowei Long +2
We present a parallel algorithm for computing -approximate mincost flow on an undirected graph with edges, where capacities and costs are assigned to both edges and vert…
Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak +1
We show the existence of length-constrained expander decomposition in directed graphs and undirected vertex-capacitated graphs. Previously, its existence was shown only in undirect…
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…
Near-Optimal Deterministic Vertex-Failure Connectivity Oracles
Yaowei Long, Thatchaphol Saranurak
We revisit the vertex-failure connectivity oracle problem. This is one of the most basic graph data structure problems under vertex updates, yet its complexity is still not well-un…
Planar Distance Oracles with Better Time-Space Tradeoffs
Yaowei Long, Seth Pettie
In a recent breakthrough, Charalampopoulos, Gawrychowski, Mozes, and Weimann (STOC 2019) showed that exact distance queries on planar graphs could be answered in time by…