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

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

   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 👍 👎
• 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 👍 👎

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)