A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners

2018/12/14 by Bodwin, Greg, Patel, Shyamal · 2 citations
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1812.05778

Abstract

We give a short and easy upper bound on the worst-case size of fault tolerant spanners, which improves on all prior work and is fully optimal at least in the setting of vertex faults.

Cited by

• Sublinear Edge Fault Tolerant Spanners for Hypergraphs
• Greedy Algorithms for Shortcut Sets and Hopsets

Related

• Efficient and Simple Algorithms for Fault Tolerant Spanners
• Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
• A Polynomial Time Algorithm for Almost Optimal Vertex Fault Tolerant Spanners
• Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
• Partially Optimal Edge Fault-Tolerant Spanners