An Algorithm for Universal Maximal Dynamic Flows in a Network

Abstract

This paper presents a modification to the Ford-Fulkerson algorithm for maximal dynamic flow in a time-weighted, capacitated network. The modification is mild, as conjectured by Gale, and produces a shipping schedule representing what has been termed the universal maximal dynamic flow. The universal feature is that, in constructing a schedule for P periods, this same schedule is maximal when truncated to p less than P periods. A numerical example compares the temporally repeated and universal-type solutions.