# 臺灣博碩士論文加值系統

(35.172.136.29) 您好！臺灣時間：2021/07/29 08:04

:::

### 詳目顯示

:

• 被引用:0
• 點閱:115
• 評分:
• 下載:0
• 書目收藏:0
 本論文提出一 O(n) 時間複雜度的演算法來解決樹狀結構上的廣播中心點問題，使廣播中心點的數量最少。廣播按照異質郵寄模型的規則進行，需在時間限制內完成。
 In this thesis, we present a O(n)-time exact algorithm to find a broadcast strategy such that broadcasting can be completed within the time constraint and the number of centers is minimal. The given graph is a tree and broadcasting is under the heterogeneous postal model.
 口試委員會審定書 iii誌謝 vAcknowledgements vii摘要 ixAbstract xi1 Introduction 11.1 Broadcast Problem and Models . . . . . . . . . . . . . 11.2 Main Results and Thesis Organization . . . . . . . . . 22 Preliminaries 32.1 Notations and Definitions . . . . . . . . . . . . . . . . 32.2 Related Works . . . . . . . . . . . . . . . . . . . . . . 53 A Linear-Time Algorithm 73.1 Algorithm Description . . . . . . . . . . . . . . . . . . 73.2 Finding SUCC(v) and b_time(v) . . . . . . . . . . . . 93.3 Evaluatng spare(v) . . . . . . . . . . . . . . . . . . . . 11xiii3.4 A Non-Sorting Method . . . . . . . . . . . . . . . . . . 123.5 Time Complexity . . . . . . . . . . . . . . . . . . . . . 164 Correctness 194.1 Minimum Unused Edges and Broadcast Time . . . . . 204.2 Earliest Spare Time . . . . . . . . . . . . . . . . . . . 234.3 Correctness of the Algorithm . . . . . . . . . . . . . . 245 Two Illustrative Examples 295.1 The First Example . . . . . . . . . . . . . . . . . . . . 295.2 The Second Example . . . . . . . . . . . . . . . . . . . 396 Conclusion 47Bibliography 49