A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners

DOI10.1145/3293611.3331588zbMATH Open1497.68368arXiv1812.05778OpenAlexW2963915537MaRDI QIDQ5145268FDOQ5145268

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)

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.

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

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
• [[:Publication:4542536|Title not available (Why is that?)]]
• 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

zbMATH Keywords

greedy algorithmsfault-tolerant spanners

Mathematics Subject Classification ID

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

Cited In (5)

• Graph spanners: a tutorial review
• Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners
• Improved approximations for relative survivable network design
• Efficient and Simple Algorithms for Fault-Tolerant Spanners
• 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)