Premium
A linear algorithm for finding the k ‐broadcast center of a tree
Author(s) -
Harutyunyan Hovhannes A.,
Liestman Arthur L.,
Shao Bin
Publication year - 2009
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.20270
Subject(s) - vertex (graph theory) , computer science , graph , algorithm , dissemination , prim's algorithm , unit disk graph , tree (set theory) , combinatorics , mathematics , theoretical computer science , shortest path tree , telecommunications , wireless network , wireless
The term k ‐broadcast indicates the process of disseminating a message from one vertex to all vertices of a graph in such a way that in each time unit, an informed vertex can send the message to up to k of its neighbors. The k ‐broadcast center of a graph is the set of vertices that can initiate a minimum time k ‐broadcast within the graph. We present a linear algorithm to determine the k ‐broadcast center of a given tree. From this, we obtain a linear time algorithm for finding the k ‐broadcast time of any vertex of the tree and, thus, the k ‐broadcast time of the tree itself. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009