David Eppstein – Publications

Publications with Christian Scheideler

• The effect of faults on network expansion.
  A. Bagchi, A. Bhargava, A. Chaudhary, D. Eppstein, and C. Scheideler.
  arXiv:cs.DC/0404029.
  16th ACM Symp. Parallelism in Algorithms and Architectures, Barcelona, 2004, pp. 286–293.
  Theory of Computing Systems 39 (6): 903–928, 2006.

  Studies the resilience of distributed computation networks against adversarial and random fault models; shows that, in both models, certain networks can withstand constant fault probabilities and still contain a large subnetwork with similar expansion to the original.