Brief announcement: better speedups for parallel max-flow

We present a parallel solution to the Maximum-Flow (Max-Flow) problem, suitable for a modern many-core architec-ture. We show that by starting from a PRAM algorithm, following an established “programmer’s workflow ” and tar-geting XMT, a PRAM-inspired many-core architecture, we achieve significantly higher speed-ups than previous approaches. Comparison with the fastest known serial max-flow imple-mentation on a modern CPU demonstrates for the first time potential for orders-of-magnitude performance improvement for Max-Flow. Using XMT, the PRAM Max-Flow algorithm is also much easier to program than for other parallel plat-forms, contributing a powerful example toward dual valida-tion of both PRAM algorithmics and XMT