Maximal Flow with Gains through a Special Network

Abstract

This paper uses the special structure at a (directed) acyclic network with positive gains to develop an extremely simple and powerful algorithm for maximal flow. Finiteness of the algorithm is achieved through a theorem characterizing basic solutions for this special network.