Problems for talk on "Construction of minimum weight spanners":

1) Prove that the greedy spanner algorithm (with parameter t) in fact
does construct a t-spanner for an arbitrary edge-weighted graph.

2) Assume that the input graph G has a linear number of edges (in the
number of nodes). Argue that a naive implementation of the greedy
spanner algorithm runs in O(n^2 log n) time, where n is the number of
nodes in G.

3) Write up the primal and dual of the used LP formulation, but
without the use of indicator variables (delta-variables).