Step graphs and their application to the organization of commodity flows in networks

Abstract

The concepts of step graphs and networks in which the edges are divided into ordered classes (shortage classes) are introduced. Each path in such graphs is assigned a tuple (an ordered sequence of nonnegative integers). The tuples are compared lexicographically. The problem of finding the path with the minimum tuple according to this ordering is stated. Functionals are compared using the lexicographic rule. An algorithm for finding the optimal path is described, and the relationship between step networks and weighted networks is investigated. The proposed formalism is applied to the problem of filling a network subject to constraints imposed on communication line capacities with communication flows under the condition that requests for the organization of such flows arrive to the network sequentially in time and the filling strategy must maximize the number of satisfied requests. The idea of an algorithm for the approximate solution of the integer multicommodity problem that uses the concepts of step networks and sequential algorithms is proposed.