在權重樹上尋找具時間限制的廣播中心問題

Finding a Broadcast Median with Time Constraint on a Weighted Tree

黃子瑋(Zih-Wei Huang)

指導教授 ： 陳健輝

共同指導教授 ： 林清池(Ching-Chi Lin)

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201801275

摘要

本論文提出一個演算法來解決在郵政模型中的權重樹上找出一個具時間限制的廣播中心問題。給定一權重樹 T = (V,E) 及時間限制 t ，在郵政模型的規則下傳播，邊的權重在此用來表示相鄰兩點間傳送資訊所需的時間，時間限制 t 指的是所有點接受到訊息的時間不能超出 t 。在此論文中我們希望能夠找出一個最佳的廣播中心，使得廣播訊息給樹中所有點所花費的時間總和最小，且所有的點都能在時間 t 內接收到訊息，同時我們的演算法也會得到整顆樹的最佳廣播時間，以及最佳的廣播順序。在這篇論文中我們結合了動態規劃法還有匈牙利演算法，提出一個 O(min(t,n) · n4) 時間複雜度的演算法來解決這個問題。

關鍵字

廣播問題 ； 廣播中心點 ； 時間限制 ； 動態規劃法 ； 權重樹 ； 郵政模型

並列摘要

We propose the problem of finding a broadcast median on a weighted tree with time con- straint under the postal model. Given a weighted tree T = (V,E) with time constraint t, the overall delay of a vertex v ∈ V (T ), is the minimum sum of the transmission time required to send a message from v to all vertices in T , and the medain is the node that has the minimum overall delay. Time constraint t denotes that all nodes in T should receive the message before time t.In this thesis, weproposean O(min(t,n)·n4) time complexity algorithm that uses dynamic programming and Hungarian Algorithm to find a median in T with time constraint.

並列關鍵字

broadcasting problem ； broadcast median ； time constraint ； dynamic programming ； weighted tree ； postal model

參考文獻

[1] P. J. Slater, E. J. Cockayne, and S. T. Hedetneniemi, “Informatiom of dissem- ination in trees,” SIAM Journal on Computing, vol. 10, no. 4, pp. 692–701, 1981.

[2] A. Jakoby, R. Reischuk, and C. Shindelhauer, “The complexity of broad- casting in planar and decomposable graphs,” Discrete Applied Mathematics, vol. 83, pp. 179–206, 1998.

[3] G. Kortsarz and D. Peleg, “Approximation algorithms for minimum time broadcast,” SIAM Journal on Discrete Mathematics, vol. 8, pp. 401–427, 1995.

[4] M. Elkin and G. Kortsarz, “Sublogarithmic approximation for telephone mul-ticast,” Journal of Computerand System Sciences,vol.72,pp.648–659,2006.

[5] A. Bar-Noy, S. Guha, J. Naor, and B. Schieber, “Multicasting in heteroge- neousnetwork,” Proceedings of the 13th ACM Symposiumon Theory of Computing, pp. 448–453, 1998.