Reliable Spanners for Metric Spaces
From MaRDI portal
Abstract: A spanner is reliable if it can withstand large, catastrophic failures in the network. More precisely, any failure of some nodes can only cause a small damage in the remaining graph in terms of the dilation, that is, the spanner property is maintained for almost all nodes in the residual graph. Constructions of reliable spanners of near linear size are known in the low-dimensional Euclidean settings. Here, we present new constructions of reliable spanners for planar graphs, trees and (general) metric spaces.
Recommendations
- An Optimal Dynamic Spanner for Doubling Metric Spaces
- Searching for realizations of finite metric spaces in tight spans
- Trimming of metric spaces and the tight span
- On minimum spanning tree-like metric spaces
- Equivalent metrics and the spans of graphs
- Sparse and thin metric spaces
- Metric spaces with expensive distances
- Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree
Cites work
- A proof of alon's second eigenvalue conjecture
- A Separator Theorem for Planar Graphs
- A spanner for the day after
- A tight bound on approximating arbitrary metrics by tree metrics
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs
- Expander graphs and their applications
- Expansion of random graphs: new proofs, new results
- Explicit construction of linear sized tolerant networks
- From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics
- Functional limit theorems for random regular graphs
- Geometric Spanner Networks
- Graph spanners
- scientific article; zbMATH DE number 2185613 (Why is no real title available?)
- scientific article; zbMATH DE number 1342092 (Why is no real title available?)
- scientific article; zbMATH DE number 1775400 (Why is no real title available?)
- scientific article; zbMATH DE number 1775403 (Why is no real title available?)
- Improved algorithms for constructing fault-tolerant spanners
- Measured descent: A new embedding method for finite metrics
- New Doubling Spanners: Better and Simpler
- Object location using path separators
- Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
- Ramsey partitions and proximity data structures
- Sometimes Reliable Spanners of Almost Linear Size.
- Sparse covers for planar graphs and graphs that exclude a fixed minor
- Strong-diameter decompositions of minor free graphs
This page was built for publication: Reliable Spanners for Metric Spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075742)
