An alternate linear algorithm for the minimum flow problem

Abstract

We present an alternate linear algorithm for finding the minimum flow in (s, t)-planar networks using a new concept of minimal removable sets developed here. The iterative nature of the algorithm facilitates the adjustment of solutions for systems in developmental stages. The minimum flow algorithm presented here requires O(|V|) time, where V denotes the set of vertices. The minimum flow problem arises in many transportation and communication systems.

Keywords:

• communication
• minimum flow
• transportation