Department of MathematicsToday many essential utilities depend on networks distributed over the surface of the Earth: water mains, electrical wires, fiber optic networks. A natural disaster or a hostile attack can put the service out of commission with great hardship to the civilian population.
We will assume that natural disasters strike at random, whereas hostile attacks will be directed to cause maximum disruption of the network. We first present a general algorithm for dealing with this set of problems by formulating them as problems of optimal augmentation of the network within constraints on the cost of adding back-up links. We then discuss some strategies for solution.