Minimizing broadcast costs under edge reductions in tree networks

We study the broadcasting of messages in tree networks under edge reductions. When an edge is reduced, its cost becomes zero. Edge reductions model the decrease or elimination of broadcasting costs between adjacent nodes in the network. Let T be an n-vertex tree and B be a target broadcast cost. We...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 1999, Vol.91 (1), p.93-117
Main Authors: Hambrusch, Susanne E., Lim, Hyeong-Seok
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Analysis of algorithms
Applied sciences
Blocking communication model
Computer science
control theory
systems
Exact sciences and technology
Message broadcasting
Operational research and scientific management
Operational research. Management science
Optimization. Search problems
Theoretical computing
Tree networks
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the broadcasting of messages in tree networks under edge reductions. When an edge is reduced, its cost becomes zero. Edge reductions model the decrease or elimination of broadcasting costs between adjacent nodes in the 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 reduce so that a broadcast initiated at an arbitrary vertex of T costs at most B. Characterizations of where edge reductions are placed underly both algorithms and imply that reduced edges can be centrally located.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(98)00121-8