Broadcasting in weighted trees under the postal model

详细信息    查看全文

• 作者：Yu-Hsuan Su^a ; ^{yhsuq@eda.ee.ntu.edu.tw" class="auth_mail" title="E-mail the corresponding author} ; Ching-Chi Lin^b ; ^{lincc@mail.ntou.edu.tw" class="auth_mail" title="E-mail the corresponding author} ; D.T. Lee^a ; ^c ; ^d ; ^{dtlee@iis.sinica.edu.tw" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Algorithm ; Broadcast center ; Weighted tree ; Postal model
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：28 March 2016
• 年：2016
• 卷：621
• 期：Complete
• 页码：73-81
• 全文大小：387 K

文摘

Given a weighted graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000554&_mathId=si1.gif&_user=111111111&_pii=S0304397516000554&_rdoc=1&_issn=03043975&md5=f4fb90a890bad38578af959e3fb5da4b" title="Click to view the MathML source">G=(V,E)class="mathContainer hidden">class="mathCode">$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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000554&_mathId=si2.gif&_user=111111111&_pii=S0304397516000554&_rdoc=1&_issn=03043975&md5=1be7c4abc9b5e7319508fb18a8bac2c9" title="Click to view the MathML source">O(n)class="mathContainer hidden">class="mathCode">$O(n)$-time algorithm in unweighted trees and Koh and Tcha [23] designed an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000554&_mathId=si252.gif&_user=111111111&_pii=S0304397516000554&_rdoc=1&_issn=03043975&md5=0f23a12397c0e91eff47e36178f1ed75" title="Click to view the MathML source">O(nlog⁡n)class="mathContainer hidden">class="mathCode">$O(n\log n)$-time algorithm in unweighted trees under the telephone model. In this paper, we strengthen the results of Slater et al. by showing an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000554&_mathId=si2.gif&_user=111111111&_pii=S0304397516000554&_rdoc=1&_issn=03043975&md5=1be7c4abc9b5e7319508fb18a8bac2c9" title="Click to view the MathML source">O(n)class="mathContainer hidden">class="mathCode">$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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000554&_mathId=si2.gif&_user=111111111&_pii=S0304397516000554&_rdoc=1&_issn=03043975&md5=1be7c4abc9b5e7319508fb18a8bac2c9" title="Click to view the MathML source">O(n)class="mathContainer hidden">class="mathCode">$O(n)$ time.