## Abstract

Spanners are sparse subgraphs that preserve distances up to

a given factor in the underlying graph. Recently spanners have found

important practical applications in metric space searching andmessage

distribution in networks. These applications use some variant of the so-

called greedy algorithm for constructing the spanner — an algorithm that

mimics Kruskal’s minimum spanning tree algorithm. Greedy spanners

have nice theoretical properties, but their practical performance with

respect to total weight is unknown. In this paper we give an exact al-

gorithm for constructing minimum-weight spanners in arbitrary graphs.

By using the solutions (andlower bounds) from this algorithm, we ex-

perimentally evaluate the performance of the greedy algorithm for a set

of realistic problem instances

a given factor in the underlying graph. Recently spanners have found

important practical applications in metric space searching andmessage

distribution in networks. These applications use some variant of the so-

called greedy algorithm for constructing the spanner — an algorithm that

mimics Kruskal’s minimum spanning tree algorithm. Greedy spanners

have nice theoretical properties, but their practical performance with

respect to total weight is unknown. In this paper we give an exact al-

gorithm for constructing minimum-weight spanners in arbitrary graphs.

By using the solutions (andlower bounds) from this algorithm, we ex-

perimentally evaluate the performance of the greedy algorithm for a set

of realistic problem instances

Original language | English |
---|---|

Pages | 797-808 |

Number of pages | 12 |

Publication status | Published - 2004 |

## Keywords

- spanners
- graphs
- Algorithms