We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
An Optimal Disjoint Pair of Additive Spanners for the 3D Grid.
- Authors
Krumme, David W.
- Abstract
A spanner of a connected graph G is a spanning connected subgraph S. If DG(u, v) and DS(u, v) denote the distance between vertices u and v in G and S, respectively, then S is an f(x)-spanner if and only if DS(u, v) ≤ f(DG(u, v)). The value f(x) - x is the delay of the spanner. An additive spanner is one with constant delay. Given a graph G and function f(x), an interesting problem is to partition the edges of G so as to define edge-disjoint f(x)-spanners of G. This paper exhibits a pair of (x + 4)-spanners for the infinite three dimensional grid, and shows that 4 is the least integer K for which there exists an edge-disjoint pair of delay-K spanners. spanner, grid, additive spanner, parallel network.
- Publication
Parallel Processing Letters, 1998, Vol 8, Issue 2, p251
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626498000262