Optimal Defense of Multi-Commodity Networks

Abstract

The determination of an optimal strategy for reinforcing arcs and nodes in a multi-commodity network is discussed. This strategy will maximize the effort required by an attacker to render the network useless. Under certain assumptions this problem is shown to be equivalent to the problem of maximizing the capacity of the minimal multi-commodity disconnecting set for the network. An algorithm for determining an optimal reinforcing strategy under these assumptions is presented, and computational results are discussed.