3 ms·

> Almost-Linear-Time Algorithm From O(mn) to O(m) ... thus excluding N (number of vertices) from computation ... Too good to be true?

• progbits 2y ago
  Constant factor so large it's going to be slower than existing (asymptotically worse) algorithms on any practical inputs. Still, a neat theoretical result.
  • 8474_s 2y ago
    The constant factors could be optimized or even accelerated with special-purpose hardware. There could be a simplification or even something like reuse/caching/memoization that in real world will reduce the constant factor significantly.
    • Jabbles 2y ago
      Maybe, but that would be a different research project. The constant factors are currently so large that even multiple orders of magnitude speedups would not make this practical.