Network topologies should be designed to provide resilience against link failures. A network with good resilience properties is referred to as a survivable network. There are many possible measures of resilience. k-Connectivity is often used as a design criterion. We present a primal-dual approximation algorithm due to Goemans and Williamson. A local search procedure for survivable network design is also discussed.
The reliability polynomial is a probabilistic measure of network reliability. The difficulty is calculating its factors, a problem which is NP-complete. We present a randomized method to calculate these factors approximately. Some special topologies with known resilience robustness are discussed, ...