Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer k, every n-node graph has a (2k – 1)-spanner on O(f1–1/kn1+1/k) edges resilient to f vertex faults, and there are examples of input graphs on which this bound cannot be improved. However, …