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.