Minimizing broadcast costs under edge reductions in tree networks

We study the broadcasting of messages in tree networks under edge reduction s. When an edge is reduced, its cost becomes zero. Edge reductions model th e decrease or elimination of broadcasting costs between adjacent nodes in t he network. Let T be an n-vertex tree and B be a target broadcast cost. We present an O(n)-time algorithm for determining the minimum number of edges of T to reduce so that a broadcast cost of B can be achieved. We present an O(n log n)-time algorithm to determine the minimum number of edges to redu ce so that a broadcast initiated at an arbitrary vertex of T costs at most B. Characterizations of where edge reductions are placed underly both algor ithms and imply that reduced edges can be centrally located. (C) 1999 Elsev ier Science B.V. All rights reserved.