CaltechAUTHORS
  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 http://resolver.caltech.edu/CaltechAUTHORS:ATJfocs92

[img]
Preview
PDF
See Usage Policy.

680Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:ATJfocs92

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)


Item Type:Book Section
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:http://resolver.caltech.edu/CaltechAUTHORS:ATJfocs92
Alternative URL:http://dx.doi.org/10.1109/SFCS.1992.267781
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10824
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:26 Jun 2008
Last Modified:26 Dec 2012 10:05

Repository Staff Only: item control page