The Gap Between Greedy Algorithm and Minimum Multiplicative Spanner

Yeyuan Chen

The greedy algorithm adapted from Kruskal's algorithm is an efficient and folklore way to produce a $k$-spanner with girth at least $k+2$. The greedy algorithm has shown to be `exi…