Broadcasting in weighted trees under the postal model

Given a weighted graph G=(V,E), the broadcasting problem is to find a broadcast center such that the maximum communication time from the center to all vertices is minimized. For this problem, Slater et al. [29] proposed an O(n)-time algorithm in unweighted trees and Koh and Tcha [23] designed an O(n...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2016-03, Vol.621, p.73-81
Main Authors: Su, Yu-Hsuan, Lin, Ching-Chi, Lee, D.T.
Format: Article
Language:English
Subjects:
Algorithm
Algorithms
Broadcast center
Broadcasting
Computer simulation
Graph theory
Graphs
Mathematical models
Optimization
Postal model
Trees
Weighted tree
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a weighted graph G=(V,E), the broadcasting problem is to find a broadcast center such that the maximum communication time from the center to all vertices is minimized. For this problem, Slater et al. [29] proposed an O(n)-time algorithm in unweighted trees and Koh and Tcha [23] designed an O(nlog⁡n)-time algorithm in unweighted trees under the telephone model. In this paper, we strengthen the results of Slater et al. by showing an O(n)-time algorithm in weighted trees under the postal model. The algorithm computes the set of broadcast centers, determines the broadcast time of the broadcast centers, and an optimal broadcast scheme from one of the centers to all vertices in the tree. We further show that the broadcast time of any vertex in the tree can also be determined in O(n) time.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2016.01.031