2 citations · 3 across the 10 of their papers we have counts for
Showing 2023 · cs.DSShow all
2 papers · 2 filters
cs.DS2023
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free
Greg Bodwin, Bernhard Haeupler, Merav Parter
We study a new and stronger notion of fault-tolerant graph structures whose size bounds depend on the degree of the failing edge set, rather than the total number of faults. For a…
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…