A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners

DOI10.1145/3293611.3331588MaRDI QIDQ5145268zbMATH OpenOpenAlexFDO

Authors Greg Bodwin, Shyamal Patel

Publication date 20 January 2021

Published in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.05778

zbMATH Keywords

greedy algorithmsfault-tolerant spanners

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
• Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel
• Efficient and Simple Algorithms for Fault-Tolerant Spanners
• Fault-tolerant spanners for general graphs
• Fault tolerant spanners for general graphs
• scientific article; zbMATH DE number 1775403
• Vertex fault-tolerant spanners for weighted points in polygonal domains
• Vertex fault-tolerant spanners for weighted points in polygonal domains
• Improved algorithms for constructing fault-tolerant spanners
• Effective edge-fault-tolerant single-source spanners via best (or good) swap edges

Cited in

(5)

• Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners
• Efficient and Simple Algorithms for Fault-Tolerant Spanners
• Improved approximations for relative survivable network design
• Graph spanners: a tutorial review
• Multiple-edge-fault-tolerant approximate shortest-path trees

This page was built for publication: A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145268)