From: Dimitrios Michail (dmixdim_at_[hidden])
Date: 2008-06-26 12:16:58
Hi,
I have written a small piece of code which computes a
2k-1 multiplicative spanner (k is an integer parameter) of undirected
weighted graphs. This spanner is simply a subgraph of an input graph
which preserves shortest path distances up to a 2k-1 factor, that is the
shortest path from u to v in the spanner is at most 2k-1 times the
shortest path
from u to v in the original graph. The main benefit is that there is
always a
2k-1 spanner with O(n^{1+1/k}) edges.
The algorithm is due to Althoefer, Das, Dobkin, Joseph and Soares. It
is a simple generalization of Kruskal's algorithm (thus I used Kruskal's
algorithm
as a template). While not the fastest possible, it is simple and elegant.
Is there any place where I could upload my code for interested people to
review and comment?
Best,
Dimitris