hm... more intuitional fidgety bits. the HKMST paper they refer to has runtime

O(m^(3/2))

... which is equal to the first component of their

O(min(m^(1/2), ??)*m)