摘要
在網路的設計上，樹狀結構是建構成本比較小的，但若某一個連結斷掉可能會造成整個網路失效，此時如何快速地找到可補救的連結就相當重要；我們在此篇論文中提出幾個有效率的演算法來為每個樹邊找出可替代的邊。令樹T是圖G 的生成樹，而S V(G)是起始點的集合，T的路由成本是所有的起始點到所有點的距離總和。對一個T上的邊e而言，其替代邊f 是一個可將e取代的邊並取代後所形成的新樹擁有最小的路由成本。給定一個無向圖G和G 的一個生成樹T，本篇論文探討如何快速地為T中的每一個邊都找到替代邊，在起始點的個數為2的情況下，我們提出了一個時間複雜度為O(mlogn+n2)的演算法；而在起始點個數大於2的情況下，我們提出另一個演算法在O(mn)的時間複雜度下解掉替代邊的問題，其中m和n分別是邊和點的個數。
並列摘要
Let T be a spanning tree of a graph G and S V(G) be a set of sources. The routing cost of T is the total distance from all sources to all vertices. For an edge e of T, the swap edge of e is the edge f minimizing the routing cost of the tree formed by replacing e with f. Given an undirected graph G and a spanning tree T of G, we investigate the problem of finding the swap edge for every tree edge. In this thesis, we propose an O(mlogn+n2)-time algorithm for the case of two sources and an algorithm with time complexity O(mn) for the case of more than two sources, in which m and n are the numbers of edges and vertices of G, respectively.
參考文獻
延伸閱讀
- Liao, C. C. (2009). 有序樹之限制性嵌入問題研究 [master's thesis, National Chi Nan University]. Airiti Library. https://doi.org/10.6837/NCNU.2009.00178
- Lin, C. C. (2007). 各種圖類上的生成樹問題 [doctoral dissertation, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2007.02072
- 李政緯（2014）。在稀疏可分枝節點下解決有向性Steiner Tree問題的近似演算法〔碩士論文，國立清華大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0016-2912201413553988
- 林明甫（2005）。The Study of Multicast Based on One Way Function Tree〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2005.00599
- Chen, S. Y. (2006). Blockage-Aware Routing Tree Construction with Buffer and Flip Flop Insertion [master's thesis, National Tsing Hua University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0016-1303200709291256