A fast parallel algorithm for minimum-cost small integral flows

Andrzej Lingas, Mia Persson

We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multi-variate polynomials over a fin…