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
![]()
|
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: |
| ||||||
ORCID: |
| ||||||
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