Premium
Multiple message broadcasting in communication networks
Author(s) -
Kwon OhHeum,
Chwa KyungYong
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230260409
Subject(s) - broadcasting (networking) , computer science , node (physics) , upper and lower bounds , graph , computer network , binary logarithm , set (abstract data type) , broadcast communication network , tree (set theory) , theoretical computer science , combinatorics , mathematics , mathematical analysis , structural engineering , engineering , programming language
Broadcasting refers to the process of dissemination of a set of messages originating from one node to all other nodes in a communication network. We assume that, at any given time, a node can transmit a message along at most one incident link and simultaneously receive a message along at most one incident link. We first present an algorithm for determining the amount of time needed to broadcast k messages in an arbitrary tree. Second, we show that, for every n , There exists a graph with n nodes whose k ‐message broadcast time matches the trivial lower bound ⌈ log n ⌉ + k − 1 by designing a broadcast scheme for complete graphs. We call those graphs minimal broadcast graphs. Finally, we construct an n node minimal broadcast graph with fewer than (⌈log n ⌉ + 1)2 ⌈ log n ⌉ −1 edges.