Analysis of edge deletion processes on faulty random regular graphs

Random regular graphs are, at least theoretically, popular communication networks. The reason for this is that they combine low (that is constant) degree with good expansion properties crucial for efficient communication and load balancing. When any kind of communication network gets large one is fa...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2003-03, Vol.297 (1), p.241-260
Main Authors: Goerdt, Andreas, Molloy, Mike
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Fault tolerance
Graph theory
k-Core
Mathematics
Random faults
Random regular graphs
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Random regular graphs are, at least theoretically, popular communication networks. The reason for this is that they combine low (that is constant) degree with good expansion properties crucial for efficient communication and load balancing. When any kind of communication network gets large one is faced with the question of fault tolerance of this network. Here, we consider the question: Are the expansion properties of random regular graphs preserved when each edge gets faulty independently of other edges with a given fault probability? We improve previous results on this problem in two respects: First, expansion properties are preserved for much higher fault probabilities than known before. Second, our results apply to random regular graphs of any degree which is at least 4. Previous results apply only to degrees of at least 42. Moreover, the techniques used by us are more elementary than those used in previous work in this area.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(02)00640-0