About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
PODC 1986
Conference paper
On fault tolerant routings in general networks
Abstract
We construct fault tolerant routings for several families of graphs, including all graphs of maximal degree less than cm1/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].