Speelman and Tang's Algorithm Runs in Almost Linear Time

Algorithm uses a low stretched spanning tree, which is an internal backbone that captures many of the network's most salient features. Given such a tree, there's always at least one good cycle you can build by adding a single link from outside the tree. So having a low stretching tree drastically reduces the number of cycles you need to consider. Even then, for the algrthem to run quickly, the team couldn't afford to build a brand new spanning tree at every step. Instead, they had to insure that each new cycle caused only minor ripple effects in the spanning trees so they could reuse most of their previous computations. Eventually, the researchers created an algorithm that runs in almost linear time