2 papers
cs.DS2025
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…
cs.DS2024
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…