[boost] [graph] multiplicative spanner code

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