Optimal fault-tolerant linear arrays

ABSTRACT

This paper proves that for every positive integers n and k, we can explicitly construct a graph G with n+O(k) vertices and maximum degree 3, such that even after removing any k vertices from G, the remaining graph still contains a path of length n-1. This settles a problem raised by Zhang [11, 12] in connection with the design of fault-tolerant linear arrays.

REFERENCES

• 1: N. Alon , F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics, v.72 n.1-3, p.15-19, December 1988 [doi>10.1016/0012-365X(88)90189-6]
• 2: Jehoshua Bruck , Robert Cypher , Ching-Tien Ho, Fault-Tolerant Meshes with Small Degree, SIAM Journal on Computing, v.26 n.6, p.1764-1784, Dec. 1997 [doi>10.1137/S0097539794274994]
• 3: Shantanu Dutt , John P. Hayes, Designing fault-tolerant systems using automorphisms, Journal of Parallel and Distributed Computing, v.12 n.3, p.249-268, July 1991 [doi>10.1016/0743-7315(91)90129-W]
• 4: Erdös, P., Graham, R., and Szemerédi, E. On sparse graphs with dense long paths. Comp. and Math. with Appl. 1 (1975), 145--161.
• 5: Gabber, O., and Galil, Z. Explicit constructions of linear-sized superconcentrators. Journal of Computer and System Sciences 22 (1981), 407--420.
• 6: Harary, F., and Hayes, J. Node fault tolerance in graphs. Networks 27 (1996), 19--23.
• 7: Hayes, J. A graph model for fault-tolerant computing systems. IEEE Trans. on Comput. C-25 (1976), 875--883.
• 8: Paoli, M., Wong, W., and Wong, C. Minimum k-hamiltonian graphs, II. J. Graph Theory 10 (1986), 79--95.
• 9: S. Ueno , A. Bagchi , S. L. Hakimi , E. F. Schmeichel, On minimum fault-tolerant networks, SIAM Journal on Discrete Mathematics, v.6 n.4, p.565-574, Nov. 1993 [doi>10.1137/0406044]
• 10: Wong, W., and Wong, C. Minimum k-hamiltonian graphs. J. Graph Theory 8 (1984), 155--165.
• 11: Li Zhang, Fault tolerant networks with small degree, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.64-69, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341809]
• 12: Li Zhang, Fault-Tolerant Meshes with Small Degree, IEEE Transactions on Computers, v.51 n.5, p.553-560, May 2002 [doi>10.1109/TC.2002.1004594]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Design, Measurement, Performance, Reliability, Theory, Verification

Keywords:
expander, fault-tolerant graph, linear array, magnifier