A k-spanner on n nodes is a directed graph G = (V, E) with V = {1,...,n}, such that for every pair of nodes (i, j), where i