2014 · 35 citations · 36 references
ComputingComputer ScienceMathematicsDistributed SystemsFault ToleranceFault-tolerant SystemsGraph TheoryNetwork Fault ToleranceNetwork ReliabilityNetwork RobustnessReliability BoundsSubgraph Isomorphism
A (1+ε)-spanner for a doubling metric (X, δ) is a subgraph H of the complete graph corresponding to (X, δ), which preserves all pairwise distances to within a factor of 1 + ε. A natural requirement from a spanner, which is essential for many applications (mainly in distributed systems or wireless networks), is to be robust against vertex and edge failures -- so that even when some vertices and edges in the network fail, we still have a (1 + ε)-spanner for what remains. The spanner H is called a k-fault-tolerant (1 + ε)-spanner, for 1 ≤ k ≤ n -- 2, if for any F ⊆ X with |F| ≤ k, the graph H -- F (obtained by removing from H the vertices of F and their incident edges) is a (1 + ε)-spanner for X -- F.
36
On sparse spanners of weighted graphs
Ingo Althöfer, Gautam Das, David Dobkin et al. · Discrete & Computational Geometry · 1993 · 600 citations · Full text
Navigating nets: simple algorithms for proximity search
Robert Krauthgamer, James R. Lee · 2015 · 319 citations