Re:Short algorithm, long-range consequences
by pshc on Friday March 01, 2013 @05:37PM
(#5307418)
That's pretty much what I gleaned too. The paper specifies how an acceptable ("low-stretch") spanning tree is shaped, and bounds [something, error criterion?] as part of its complexity proof.
[ Parent
| on HN ]
So I guess the bulk of the brainwork in producing this result was in a) deriving the low-stretch spanning tree definition and algorithm, and b) proving the performance bound? Because, aside from understanding the low-stretch spanning tree calculation, the algorithm is indeed pretty simple.
Actually, I should add: one other tricky is coming up with (the probability distribution for) how you choose the order in which to restore edges.