Does anyone know if these algorithms are practical on real problems on real machines, or is the constant term large enough you would normally just use a more traditional algorithm for most work?
The constants are enormous enough that you'd never want to use these algorithms in practice - for now, at least. There's a key problem that uf resolved would allow quite efficient implementations of this family of algorithms even on the GPU, something that previously wasn't really possible for such graph algorithms.