Broadcasting in Heterogeneous Tree Networks with Edge Weight Uncertainty

Abstract

A broadcasting problem in heterogeneous tree networks with edge weight uncertainty under the postal model is considered in this paper. The broadcasting problem asks for a minmax-regret broadcast center, which minimizes the worst-case loss in the objective function. Due to the presence of edge weight uncertainty, it is not easy to attack the broadcasting problem. An $O(n\log n\log \log n)$-time algorithm is proposed for solving the broadcasting problem.