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

[img]
Preview
PDF
See Usage Policy.

696kB

Use this Persistent URL to link to this item: https://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
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/SFCS.1992.267781DOIUNSPECIFIED
ORCID:
AuthorORCID
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
DOI:10.1109/SFCS.1992.267781
Record Number:CaltechAUTHORS:ATJfocs92
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:ATJfocs92
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10824
Collection:CaltechAUTHORS
Deposited By:INVALID USER
Deposited On:26 Jun 2008
Last Modified:08 Nov 2021 21:11

Repository Staff Only: item control page