Dimitri Watel


ADAPTIVE NETWORK FLOW



We are here interested in building a robust flow in case of an attack. We want to size a flow network such that a maximum flow may go from the source to the sink and such that the flow resists to the destruction of some of the arcs of the network. When an arc is destroyed, the residual flow is a maximum flow where the flow on each arc is no more the initial flow. This constraint is due to the fact that the attack occurs on an existing physical network, and it is unlikely that this network can be resized, then the capacity of the arcs cannot be upgraded after the attacks.

For instance, on the figure on the right, the residual flow after the destruction of (s,T) and (N,E) is 1, because the flow of (N,T) is 1, thus the residual flow cannot be more that 1 on that arc and on the unique remaining path between the source and the sink. We know the number of arcs that will be attacked but not the arcs themselves. Thus we must anticipate all the possible attacks so that the residual flow is maximum: we want to optimize the worst case. On the example, a good solution would be to add more flow on the arc (N, T) and on the arcs (Y, N) and (T, N) so that we can redirect more flow after the attack.



Publications

Conférences sans acte

[RWPP17] T. Ridremont, D. Watel, P.-L. Poirion, and C. Picouleau. Flot adaptatif maximum pour la destruction de k arcs, Février 2017. ROADEF.
[RWPP18a] T. Ridremont, D. Watel, P.-L. Poirion, and C. Picouleau. Flot adaptatif maximum pour la destruction de k arcs, Février 2018. ROADEF.
[RWPP18b] T. Ridremont, D. Watel, P.-L. Poirion, and C. Picouleau. Flot adaptatif maximum pour la destruction de k arcs, Septembre 2018. OR.

This list was generated by bibtex2html 1.98.


Change language : Français English