Maximal, Lexicographic, and Dynamic Network Flows

This paper proves two properties of maximal network flows: (1) If there exist a maximal network flow with a given departure pattern at the sources and a maximal flow with a given arrival pattern at the sinks, then there exists a flow that has both this departure pattern at the sources and this arrival pattern at the sinks. (2) There exists a maximal dynamic network flow that simultaneously has a latest (earliest) departure schedule at the sources and an earliest (latest) arrival schedule at the sinks. The paper modifies Ford and Fulkerson's maximal dynamic flow algorithm to construct a maximal dynamic network flow with a latest departure schedule and an earliest arrival schedule.