test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works

Advanced Search
& Collections
Issue Date   
Sign on to:   
Receive email
My Account
authorized users
Edit Profile   
About T-Space   

T-Space at The University of Toronto Libraries >
University of Toronto at Scarborough >
Computer and Mathematical Science >
Mathematics >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/9482

Title: Analysis of edge deletion processes on random regular graphs.
Authors: Goerdt, A.
Molloy, M.
Keywords: analysis of edge deletion process
random regular graphs
Issue Date: 2003
Publisher: Elsevier
Citation: Goerdt,A., Molloy, M. Analysis of edge deletion processes on faulty random regular graphs. Theor. Comput. Sci. 1-3(297): 241-260 (2003)
Abstract: 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.
Description: 2002 Elsevier Science B.V. All rights reserved. journal homepage website http://www.informatik.uni-trier.de/~ley/db/journals/tcs/tcs297.html
URI: http://hdl.handle.net/1807/9482
ISSN: 0304-3975
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
Journal version analysis of edge deletion processs on faulty random regular graphs.pdf226.58 kBAdobe PDF
Journal version analysis of edge deletion processs on faulty random regular graphs.pdf.txt41.99 kBText

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.