A Caltech Library Service

Fault tolerant graphs, perfect hash functions and disjoint paths

Ajtai, M. and Alon, N. and Bruck, J. and Cypher, R. and Ho, C.T. and Naor, M. and Szemerédi, E. (1992) Fault tolerant graphs, perfect hash functions and disjoint paths. In: 33rd Annual Symposium on Foundations of Computer Science, 1992. IEEE , Piscataway, NJ, pp. 693-702. ISBN 0818629002.

See Usage Policy.


Use this Persistent URL to link to this item:


Given a graph G on n nodes the authors say that a graph T on n + k nodes is a k-fault tolerant version of G, if one can embed G in any n node induced subgraph of T. Thus T can sustain k faults and still emulate G without any performance degradation. They show that for a wide range of values of n, k and d, for any graph on n nodes with maximum degree d there is a k-fault tolerant graph with maximum degree O(kd). They provide lower bounds as well: there are graphs G with maximum degree d such that any k-fault tolerant version of them has maximum degree at least Ω(d√k)

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Alon, N.0000-0003-1332-4883
Bruck, J.0000-0001-8474-0812
Additional Information:© Copyright 1992 IEEE. Reprinted with permission. Publication Date: 24-27 Oct. 1992. Research supported in part by a United States Israel BSF Grant.
Subject Keywords:computational geometry; fault tolerant computing; file organization; graph theory; disjoint paths; k-fault tolerant graph; perfect hash functions; performance degradation
Record Number:CaltechAUTHORS:ATJfocs92
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10824
Deposited On:26 Jun 2008
Last Modified:08 Nov 2021 21:11

Repository Staff Only: item control page