Premium
Local broadcasting in a tree under minisum criterion
Author(s) -
Koh JaeMoon,
Tcha DongWan
Publication year - 1993
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.3230230109
Subject(s) - vertex (graph theory) , broadcasting (networking) , tree (set theory) , computer science , set (abstract data type) , sequence (biology) , mathematics , combinatorics , computer network , graph , biology , genetics , programming language
Abstract This paper is concerned with information dissemination in a tree. It is assumed that a vertex can either transmit or receive a message and an informed vertex can transmit it to only one of its neighbors at a time. Under a minisum criterion, a necessary and sufficient condition for an optimal call sequence at each vertex is established. Based on this, an O ( N log N ) algorithm is designed to find optimal call sequences at all vertices and to determine the broadcast center of a tree—the set of all vertices from which minisum broadcasting can be accomplished. © 1993 John Wiley & Sons, Inc.