Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 1992 | public
Book Section - Chapter Open

Fault tolerant graphs, perfect hash functions and disjoint paths

Abstract

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)

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.

Files

AJTfocs92.pdf
Files (696.6 kB)
Name Size Download all
md5:bede900993934714b3a406c5427a214a
696.6 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 16, 2023