Step graphs and their application to the organization of commodity flows in networks
- Authors: Grinberg Y.R.1
-
Affiliations:
- Kharkevich Institute for Information Transmission Problems
- Issue: Vol 55, No 2 (2016)
- Pages: 222-231
- Section: Computer Methods
- URL: https://journals.rcsi.science/1064-2307/article/view/219581
- DOI: https://doi.org/10.1134/S1064230716020040
- ID: 219581
Cite item
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.
About the authors
Ya. R. Grinberg
Kharkevich Institute for Information Transmission Problems
Author for correspondence.
Email: greenjak@yandex.ru
Russian Federation, Bolshoi Karetnyi per. 19, Moscow, 127051