Trofymchuk O.M., Vasyanin V.A.
Choosing the capacity of arcs with constraint on flow delay time

The authors consider the problem of choosing the capacity of arcs from a given set, which is important in flow distribution in multicommodity communication networks with constraint on flow delay time. Such problem is proved to be NP-hard. The algorithms for the approximate solution of the problem and results of their experimental comparison with exact algorithm based on generating a sequence of binary reflected Gray codes are given. It is noted that obtaining an exact solution is possible with the use of pseudopolynomial algorithms for the 0–1 multiple-choice knapsack problem. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: combinatorial optimization problems, flow delay time, flows in networks, Computer science, Cybernetics, Approximate solution, Binary reflected gray codes, Combinatorial optimization problems, Delay Time, Experimental comparison, Flows in networks, Multiple choice knapsack problem, Pseudopolynomial algorithms, Combinatorial optimization

Cite:
Trofymchuk O.M., Vasyanin V.A. (2019). Choosing the capacity of arcs with constraint on flow delay time. Cybernetics and Systems Analysis, 55 (4), 50-60. doi: https://doi.org/10.1007/s10559-019-00165-0 http://jnas.nbuv.gov.ua/article/UJRN-0001003093 [In Russian].