English  |  正體中文  |  简体中文  |  Items with full text/Total items : 26999/38800
Visitors : 2394494      Online Users : 65
RC Version 4.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Adv. Search

Please use this identifier to cite or link to this item: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/40456

Title: The broadcast median problem in heterogeneous postal mode
Authors: Cheng-Hsiao Tsou;Gen-Huey Chen;Hung-I Yu;Ching-Chi Lin
Contributors: 國立臺灣海洋大學:資訊工程學系
Date: 2013
Issue Date: 2017-01-19T03:00:12Z
Publisher: Journal of Combinatorial Optimization
Abstract: Abstract: We propose the problem of finding broadcast medians in heterogeneous networks. A heterogeneous network is represented by a graph G=(V,E), in which each edge has a weight that denotes the communication time between its two end vertices. The overall delay of a vertex v∈V(G), denoted as b(v,G), is the minimum sum of the communication time required to send a message from v to all vertices in G. The broadcast median problem consists of finding the set of vertices v∈V(G) with minimum overall delay b(v,G) and determining the value of b(v,G). In this paper, we consider the broadcast median problem following the heterogeneous postal model. Assuming that the underlying graph G is a general graph, we show that computing b(v,G) for an arbitrary vertex v∈V(G) is NP-hard. On the other hand, assuming that G is a tree, we propose a linear time algorithm for the broadcast median problem in heterogeneous postal model.
Relation: 25(4)
URI: http://ntour.ntou.edu.tw:8080/ir/handle/987654321/40456
Appears in Collections:[資訊工程學系] 期刊論文

Files in This Item:

File Description SizeFormat

All items in NTOUR are protected by copyright, with all rights reserved.


著作權政策宣告: 本網站之內容為國立臺灣海洋大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用,請合理使用本網站之內容,以尊重著作權人之權益。
網站維護: 海大圖資處 圖書系統組
DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback