Construction of Minimum-Weight Spanners

Mikkel Muhldorff Sigurd, Martin Zachariasen

Research output: Contribution to conferencePaper

12 Citations (Scopus)

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
Original languageEnglish
Pages797-808
Number of pages12
Publication statusPublished - 2004

Keywords

  • spanners
  • graphs
  • Algorithms

Fingerprint

Dive into the research topics of 'Construction of Minimum-Weight Spanners'. Together they form a unique fingerprint.

Cite this