Showing cs.DSShow all
3 papers · 1 filter
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.DS2023
Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
Greg Bodwin, Lily Wang
The restoration lemma is a classic result by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt [PODC '01], which relates the structure of shortest paths in a graph before and afte…
cs.DS2020
Online Generalized Network Design Under (Dis)Economies of Scale
Viswanath Nagarajan, Lily Wang
We consider a general online network design problem where a sequence of N requests arrive over time, each of which needs to use some subset of the available resources E. The cost i…