Published October 1992
| Version 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
Identifiers
- Eprint ID
- 10824
- Resolver ID
- CaltechAUTHORS:ATJfocs92
Dates
- Created
-
2008-06-26Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field