title: Easily repairable networks: reconnecting nodes after damage.
abstract: We introduce a simple class of distribution networks that withstand damage by being repairable instead of redundant. Instead of asking how hard it is to disconnect nodes through damage, we ask how easy it is to reconnect nodes after damage. We prove that optimal networks on regular lattices have an expected cost of reconnection proportional to the lattice length, and that such networks have exactly three levels of structural hierarchy. We extend our results to networks subject to repeated attacks, in which the repairs themselves must be repairable. We find that, in exchange for a modest increase in repair cost, such networks are able to withstand any number of attacks.
authors.affiliation: London Institute for Mathematical Sciences, 35a South Street, Mayfair, London W1K 2XF, United Kingdom and Unilever R&D, Colworth Science Park, MK44 1LQ Bedford, United Kingdom.
authors.forename: Robert S
authors.initials: RS
authors.lastname: Farr
authors.affiliation: Department of Mathematics, Duke University, Rayleigh-Durham, North Carolina 27708-0320, USA.
authors.forename: John L
authors.initials: JL
authors.lastname: Harer
authors.affiliation: London Institute for Mathematical Sciences, 35a South Street, Mayfair, London W1K 2XF, United Kingdom and Centre National de la Recherche Scientifique, Paris 75248, France.
authors.forename: Thomas M A
authors.initials: TM
authors.lastname: Fink