On fault tolerant routings in general networks
David Peleg, Barbara B. Simons · 1986
We construct fault tolerant routings for several families of graphs, including all graphs of maximal degree less than cnl/3 for some c > 0. With these routings, the diameter of the survival graph is bounded by a constant (e.g., 4 or 6), so long as the number of faults is less than the connectivity of the graph.This result partially confirms a conjecture of Dolev et.al. [DHSS].