A linear algorithm for finding the  k ‐broadcast center of a tree | Zendy

Harutyunyan Hovhannes A. | Zendy; Liestman Arthur L. | Zendy; Shao Bin | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research