AUGMENTING-PATH MAXFLOW ALGORITHM ON EXTENDED MIXED NETWORKS

Abstract

Graph is a powerful mathematical tool applied in many fields as transportation, communication, informatics, economy, … In an ordinary graph the weights of edges and vertexes are considered independently where the length of a path is the sum of weights of the edges and the vertexes on this path. However, in many practical problems, weights at a vertex are not the same for all paths passing this vertex, but they depend on coming and leaving edges. This paper develops a model of mixed extended network that can be applied to modelling many practical problems more exactly and effectively. The main contribution of this paper is the augmenting-path maxflow algorithm and the Maxflow-Mincut theorem on extended mixed networks.