The Maximum Flows in Planar Dynamic Networks

摘要

An nontrivial extension of the maximal static flow problem is the maximal dynamic flow model, where the transit time to traverse an arc is taken into consideration. If the network parameters as capacities, arc traversal times, and so on, are constant over time, then a dynamic flow problem is said to be stationary. Research on flow in planar static network is motivated by the fact that more efficient algorithms can be developed by exploiting the planar structure of the graph. This article states and solves the maximum flow in directed (1, n) planar dynamic networks in the stationary case.