Computation of Broadcasting Multiple Messages in a Positive Weighted Tree

Abstract

In this paper, we present algorithms for locating the vertices in a tree of $n$ vertices of positive edge-weighted tree and a positive vertex-weighted tree from which we broadcast multiple messages in a minimum cost. Their complexity is $O(n^2\log n)$. It improves a direct recursive approach which gives $O(n^3)$. In the case where all the weights are equal to one, the complexity is $O(n)$.