5 papers
Reviving Thorup's Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7
We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…
Better Bounds for Semi-Streaming Single-Source Shortest Paths
Sepehr Assadi, Gary Hoppenworth, Janani Sundaresan
In the semi-streaming model, an algorithm must process any -vertex graph by making one or few passes over a stream of its edges, use words of space…
Near-Optimal Fault-Tolerant Strong Connectivity Preservers
Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang
A -fault-tolerant connectivity preserver of a directed -vertex graph is a subgraph such that, for any edge set of size , the strongly co…
New Separations and Reductions for Directed Preservers and Hopsets
Gary Hoppenworth, Yinzhan Xu, Zixuan Xu
We study distance preservers, hopsets, and shortcut sets in -node, -edge directed graphs, and show improved bounds and new reductions for various settings of these problems.…
Covering Approximate Shortest Paths with DAGs
Sepehr Assadi, Gary Hoppenworth, Nicole Wein
We define and study analogs of probabilistic tree embedding and tree cover for directed graphs. We define the notion of a DAG cover of a general directed graph : a small collect…