time $O(m).$ The construction works as follows. Start at any vertex $v$, let $B_i$ denote the ball of radius $i$ centered at $v$, and let $|B_i|$ denote the number of vertices in $B_i$. Grow such balls around $v$ until we find an index $i$ with $|B_{i+1}| \le n^{1/k} |B_i|.$ We can clearly guarantee that $i \le k$. At this point, add a spanning tree on $B_{i+1}$ to your spanner and delete all vertices in $B_i.$ Now, recurse on the remaining graph. It is easy to check that the resulting spanner is as desired. Our algorithm for directed graphs is similar, and we give a more specific overview in \[sec:4overview\].

We gain an $O(\log\log n)$ dependence over the undirected spanner algorithm presented because we must recurse on the balls we grew instead of simply building a spanning tree on them. The precise condition for recursion and corresponding calculation are performed in the algorithms [<span style="font-variant:small-caps;">GoodCut</span>]{} (\[algo:goodcut\]) and \[lemma:inbound\].

Further, our $O(k\log k)$ approximations of \[sec:klogk\_approx\] are then achieved by using the techniques of the algorithms in \[sec:constantapprox\] to better control the size of the outballs and inballs in an invocation of the deterministic algorithm of \[sec:algo\].

Preliminaries {#sec:prelim}
=============

For weighted 