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

Advanced Search
Home   
 
Browse   
Communities
& Collections
  
Issue Date   
Author   
Title   
Subject   
 
Sign on to:   
Receive email
updates
  
My Account
authorized users
  
Edit Profile   
 
Help   
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/9480

Title: Broadcasting in Random Graphs
Authors: Frieze, A.
Molloy, M.
Keywords: broadcasting
random graphs
Issue Date: Sep-1994
Publisher: Elsevier
Citation: Frieze, A., Molloy,M. Broadcasting in Random Graphs, Discrete Math. 54 (1994) 77-79
Abstract: We do a probabilistic analysis of the problem of distributing a single piece of information to the vertices of a graph G. Assuming that the input graph G is Gn,p, we prove an O(ln n/n) upper bound on the edge density needed so that with high probability the information can be broadcast in ⌈log2 n⌉ rounds.
Description: original journal homepage website http://www.informatik.uni-trier.de/~ley/db/journals/dam/dam54.html
URI: http://hdl.handle.net/1807/9480
ISSN: 0166-218x
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
broadcasting_in_random_graphs.pdf138.5 kBAdobe PDF
View/Open
broadcasting_in_random_graphs.pdf.txt7.44 kBText
View/Open

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

uoft