Reliable Spanners for Metric Spaces

DOI10.1145/3563356arXiv2007.08738MaRDI QIDQ6075742

Sariel Har-Peled, Manor Mendel, Dániel Oláh

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

computational geometryspannersreliable

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Functional limit theorems for random regular graphs
• Expansion of random graphs: new proofs, new results
• Strong-diameter decompositions of minor free graphs
• Ramsey partitions and proximity data structures
• Explicit construction of linear sized tolerant networks
• Sparse covers for planar graphs and graphs that exclude a fixed minor
• On metric Ramsey-type phenomena
• Measured descent: A new embedding method for finite metrics
• Robust Geometric Spanners
• New Doubling Spanners: Better and Simpler
• Geometric Spanner Networks
• Expander graphs and their applications
• A proof of alon's second eigenvalue conjecture
• Graph spanners
• A Separator Theorem for Planar Graphs
• Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
• Object location using path separators
• Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
• From hierarchical partitions to hierarchical covers
• Sometimes Reliable Spanners of Almost Linear Size.
• A tight bound on approximating arbitrary metrics by tree metrics
• Improved algorithms for constructing fault-tolerant spanners

This page was built for publication: Reliable Spanners for Metric Spaces