2009 · 58 citations · 32 references
ComputingComputer ScienceMathematicsFault ToleranceFault-tolerant ComputingFault-tolerant SystemsGraph AlgorithmsGraph TheoryComputational Complexity Of Graph AlgorithmsSubgraph Isomorphism
The paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G=(V,E) and an integer k ≥ 1, the subgraph H=(V,E'), E'⊆ E, is a spanner of stretch k (or, a k-spanner) of G if δH(u,v) ≤ k· δG(u,v) for every u,v ∈ V, where δG'(u,v) denotes the distance between u and v in G'. Graph spanners were extensively studied since their introduction over two decades ago. It is known how to efficiently construct a (2k-1)-spanner of size O(n1+1/k), and this size-stretch tradeoff is conjectured to be tight.
32
Mikkel Thorup, Uri Zwick · Journal of the ACM · 2005 · 618 citations
On sparse spanners of weighted graphs
Ingo Althöfer, Gautam Das, David Dobkin et al. · Discrete & Computational Geometry · 1993 · 600 citations · Full text
Mikkel Thorup, Uri Zwick · 2001 · 521 citations
A trade-off between space and efficiency for routing tables
David Peleg, Eli Upfal · Journal of the ACM · 1989 · 350 citations · Full text
An Optimal Synchronizer for the Hypercube
David Peleg, Jeffrey D. Ullman · SIAM Journal on Computing · 1989 · 347 citations