Preplanned Recovery Schemes Using Multiple Redundant Trees in Complete Graphs

摘要

Zehavi and Itai have suggested a conjecture that implies we can use k disjoint trees to achieve up to k-1 simultaneous edge failures restoration for k-edge connected graphs or up to k-1 simultaneous node failures restoration for k-node connected graphs. In this paper, we firstly point out that a complete graph with n nodes is both (n-l)-edge connected and (n-l)-node connected. This implies that, provided that Zehavi's conjecture is right, we can use n-1 disjoint trees for restoration. Although we have not demonstrated the correctness of Zehavi's conjecture, we indeed construct two types of recovery schemes using multiple redundant trees for complete graphs, Hamilton-based recovery scheme and star-based recovery scheme, based on two types of decomposition of complete graphs. In complete graphs with n nodes, the latter can recover from any up to n-2 simultaneous link or node failures, and the former can recover from any up to n-2 simultaneous link or node failures if n is odd and any up to n-3 failures if n is even.