Information Dissemination in Trees

TLDR

Large organizations often need to disseminate information from a central office to all divisions along hierarchical reporting lines, which can be modeled as information dissemination in trees. The paper aims to determine the time needed to broadcast a unit of information from any node to all others in a tree. It presents an algorithm that computes this broadcast time. The algorithm also identifies the broadcast center, shows that its induced subtree is always a star with two or more vertices, and proves that computing the minimum broadcast time in an arbitrary graph is NP‑complete.

Abstract

In large organizations there is frequently a need to pass information from one place, e.g., the president’s office or company headquarters, to all other divisions, departments or employees. This is often done along organizational reporting lines. Insofar as most organizations are structured in a hierarchical or treelike fashion, this can be described as a process of information dissemination in trees. In this paper we present an algorithm which determines the amount of time required to pass, or to broadcast, a unit of information from an arbitrary vertex to every other vertex in a tree. As a byproduct of this algorithm we determine the broadcast center of a tree, i.e., the set of all vertices from which broadcasting can be accomplished in the least amount of time. It is shown that the subtree induced by the broadcast center of a tree is always a star with two or more vertices. We also show that the problem of determining the minimum amount of time required to broadcast from an arbitrary vertex in an arbitrarygraph is NP-complete.