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
Information and Computation
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 cn 1 3 for some c>0. With these routings, the diameter of the surviving 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. (1984, in "Proceedings, 16th ACM Symp. on Theory of Comput.," pp. 526-535). © 1987.