[Back]

W. Auzinger, K. Obelovska, R. Stolyarchuk:
"A Revised Gomory-Hu Algorithm Taking Account of Physical Unavailability of Network Channels";
Talk: 27th International Science Conference on Computer Networks CN2020, Gdansk, Poland; 2020-06-23 - 2020-06-24; in: "Computer Networks", P. Gaj, W. Gumiński, A. Kwiecień (ed.); Springer International Publishing, (2020), ISBN: 978-3-030-50718-3; 3 - 13.

The classical Gomory-Hu algorithm aims for finding, for given input flows,
a network topology for data transmission and bandwidth of its channels
which are optimized subject to minimal bandwidth criteria.
In practice, it may occur that some channels between nodes of the network are not active.
Ignoring such channels using the topology obtained by the Gomory-Hu algorithm
will not lead to an optimal flow-rate.

In this paper the focus is on a modified algorithm taking into account deficient channels.
While the classical algorithm generates a sequence of ring subnets,
in our modified version the use of deficient channels is checked
at intermediate stages in each cycle of the algorithm.
When forming ring subnets, the availability of new channels to be introduced
into the ring subnet is checked and in the case of unavailability
another ring closest to the optimal one is selected.
The network optimized by this modified algorithm guarantees
the transmission of the maximum input stream.

Network Topology, Channel Capacity, Gomory-Hu Algorithm

http://dx.doi.org/10.1007/978-3-030-50719-0_1

https://publik.tuwien.ac.at/files/publik_289288.pdf