Minimum cost flow algorithms for series-parallel networks (Q1061597)

It is shown that an acyclic multigraph with a single source and a single sink is series parallel if and only if for arbitrary linear cost functions and arbitrary capacities the corresponding minimum cost flow problem can be solved by a greedy algorithm. Furthermore, for networks of this type with m edges and n vertices, two \(O(mn+m \log m)\)-algorithms are presented. One of them is based on the greedy scheme.