Back to Search
Start Over
Optimal Broadcasting in Fully Connected Trees.
- Source :
- Journal of Interconnection Networks; Mar2023, Vol. 23 Issue 1, p1-20, 20p
- Publication Year :
- 2023
-
Abstract
- Broadcasting is disseminating information in a network where a specific message must spread to all network vertices as quickly as possible. Finding the minimum broadcast time of a vertex in an arbitrary network is proven to be NP-complete. However, this problem is solvable for a few families of networks. In this paper, we present an optimal algorithm for finding the broadcast time of any vertex in a fully connected tree ( FCT n ) in O (| V | log log n) time. An FCT n is formed by attaching arbitrary trees to vertices of a complete graph of size n where | V | is the total number of vertices in the graph. [ABSTRACT FROM AUTHOR]
- Subjects :
- BROADCASTING industry
TREES
COMPLETE graphs
GRAPH theory
Subjects
Details
- Language :
- English
- ISSN :
- 02192659
- Volume :
- 23
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Journal of Interconnection Networks
- Publication Type :
- Academic Journal
- Accession number :
- 160236585
- Full Text :
- https://doi.org/10.1142/S0219265921500377