2 citations · 3 across the 12 of their papers we have counts for
5 papers · 1 filter
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| \…