PUBLISHED PAPERS #12.02
| Volodymyr Vasyanin, Oleksandr Trofymchuk, Liudmyla Ushakova. Data Structures and Route Reduction Procedures in the Problem of Distribution and Routing of Flows in a Communication Network |
|---|
| Abstract. In the problems of the distribution and routing of flows in communication networks, the input data is vehicle routes or data transmission channels. For the distribution of flows in this problems in optimization algorithms use special data structures – abstract data types, which describe the relationship between distributed flows and routes, as well as route reduction procedures, which can significantly reduce the number of such connections. The paper develops data structures and route reduction algorithms that allow solving the problem of distribution of flows in the case when the number of specified routes is very large, and the amount of computer RAM is limited. Estimates of the time complexity of the algorithm for reducing routes by nodes and arcs, as well as the algorithm for generating a reference data structure, have been obtained. The proposed algorithms were tested on networks with the number of nodes from 50 to 500 and the number of routes from 1225 to 124750, which showed their performance, good computational efficiency and they can be used in practical problems of distribution and routing of flows on large-dimensional networks. |
| Keywords: multicommodity hierarchical networks, discrete flows, problems of combinatorial optimization, computer modeling |
 Download PDF |
| DOI: https://doi.org/10.30546/MaCoSEP2025.069 |