Loading...
Please wait, while we are loading the content...
Heuristics for generating additive spanners (2004).
| Content Provider | CiteSeerX |
|---|---|
| Author | Letourneau, Michael J. |
| Abstract | Given an undirected and unweighted graph G, the subgraph S is an additive spanner of G with delay d if the distance between any two vertices in S is no more than d greater than their distance in G. It is known that the problem of finding additive spanners of arbitrary graphs for any fixed value of d with a minimum number of edges is NP-hard. Additive spanners are used as substructures for communication networks which are subject to design constraints such as minimizing the number of connections in the network, or permitting only a maximum number of connections at any one node. In this thesis, we consider the problem of constructing good additive spanners. We say that a spanner is “good ” if it contains few edges, but not necessarily a minimum number of them. We present several algorithms which, given a graph G and a delay parameter d as input, produce a graph S which is an additive spanner of G with delay d. We evaluate each of these algorithms experimentally over a large set of input |
| File Format | |
| Publisher Date | 2004-01-01 |
| Access Restriction | Open |
| Content Type | Text |
