Complexity of resilient network optimisation
Path restoration (PR) is one of the basic mechanisms for securing telecommunication networks against failures. In the paper, we discuss the complexity of certain variants of a multi-commodity flow network optimisation problem in directed graphs related to state-independent path restoration mechanisms. We demonstrate that most variants of the considered problem are NP-hard. Depending on the variant
