๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Explicit construction of linear sized tolerant networks

โœ Scribed by N. Alon; F.R.K. Chung

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
369 KB
Volume
72
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

For every E > 0 and every integer m > 0, we construct explicitly graphs with O(m/e) vertices and maximum degree 0(1/e*), such that after removing any (1 -l ) portion of their vertices or edges, the remaining graph still contains a path of length m. This settles a problem of Rosenberg, which was motivated by the study of fault torerant linear arrays.

๐Ÿ“œ SIMILAR VOLUMES

Explicit construction of exponential siz
Explicit construction of exponential sized families of k-independent sets
โœ N Alon ๐Ÿ“‚ Article ๐Ÿ“… 1986 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 184 KB

Error correcting codes are used to describe explicit collections Fk of subsets of {1, 2,... n}, with IFkl > 2 ckn (ck > 0), such that for any selections A, B of kl and k 2 of members of Fk with kl + k2 = k, there are elements in all the members of A and not in the members of B. This settles a proble

On the Construction of Fault-Tolerant Cu
On the Construction of Fault-Tolerant Cube-Connected Cycles Networks
โœ J. Bruck; R. Cypher; C.T. Ho ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 772 KB

This paper presents a new approach to tolerating edge faults and node faults in (CCC) networks of Cube-Connected Cycles in a worst-case scenario. Our constructions of fault-tolerant CCC networks are obtained by adding extra edges to the CCC. The main objective is to reduce the cost of the fault-tole