@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",

}