2 papers
cs.DS2025
Light Edge Fault Tolerant Graph Spanners
Greg Bodwin, Michael Dinitz, Ama Koranteng +1
There has recently been significant interest in fault tolerant spanners, which are spanners that still maintain their stretch guarantees after some nodes or edges fail. This work h…
cs.DS2025
Approximation Algorithms for Optimal Hopsets
Michael Dinitz, Ama Koranteng, Yasamin Nazari
For a given graph , a "hopset" with hopbound and stretch is a set of edges such that between every pair of vertices and , there is a path with at most hop…