Network optimization problem based on tie-set graph - distributed algorithm of max-flow problem

摘要

This paper dealt with network optimization problem based on tie-set graph theory. First, theory of tie-set graph and tie-set flow vector space is introduced. Then the minimization of appropriate network evaluation function in μ dimensional tie-set flow vector space is presented. Maximum flow network problem is solved by introducing appropriate penalty (or cost) function to each edge of a network, and a tie-set based algorithm for max-flow problem is presented. Proposed method has a remarkable feature, where local and distributed optimizations with respect to each tie-set lead to the global optimization. Therefore, this method is quite suitable to network management for modern complicated information network.