@inproceedings{567a133d14ec4f0695217ca61f21704f,
title = "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 Omega (d square root k).",
author = "M. Ajtai and N. Alon and J. Bruck and R. Cypher and Ho, {C. T.} and M. Naor and E. Sz{\'e}meredi",
note = "Publisher Copyright: {\textcopyright} 1992 IEEE.; 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 ; Conference date: 24-10-1992 Through 27-10-1992",
year = "1992",
doi = "10.1109/SFCS.1992.267781",
language = "English (US)",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "693--702",
booktitle = "Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992",
address = "United States",
}