完全圖上最大權重配對問題之自我穩定演算法的設計及分析

dc.contributor.author 陳瑞宜 zh_tw
dc.contributor.author 林順喜 zh_tw
dc.contributor.author Rue-Yi Chen and Shun-Shii Lin en_US
dc.date.accessioned 2014-10-27T15:24:15Z
dc.date.available 2014-10-27T15:24:15Z
dc.date.issued 2000-04-??- zh_TW
dc.description.abstract 在1974年,Dijkstra提出了自我穩定的概念。一個分散式系統不論其初始狀態為何,最後都會收斂至正確的系統狀態稱之為自我穩定系統。近年來,自我穩定演算法不用初始化的特性受到許多研究者的重視。Hsu和Huang針對分散式網路中「最大配對」問題提出了自我穩定演算法,並利用變數函數分析法,證明了此演算法需耗用的時間複雜度為O(n3),然而Tel針對此一演算法提出不同的變數函數,證明最多需要O(n2)的時間複雜度。在本論文中,我們將自我穩定系統的理論應用在完全圖上的「最大權重配對」問題,設計出包含五個規則的自我穩定演算法,並針對此自我穩定演算法的正確性進行證明分析。最大權重問題是指當節點兩兩配對之後,其線段權重兩兩交換並不會找到更大的值,也就是除了希望在圖中找到最大配對之外,更進一步能夠使配對的權重達到最大。因此我們結合了Hsu-Huang最大配對自我穩定演算法,以及嶄新的交換配對規則,保留自我穩定系統容錯及自我穩定的特性,設計了時間複雜度為O(n2+nk)的一個最大權重配對問題之自我穩定演算法。 zh_tw
dc.description.abstract In 1974, Dijsktra defined a self-stabilizing system as a system which is guaranteed to arrive at a legitimate state in a finite number of steps regardless of its initial state. Since his introduction, self-stabilizing algorithms gained wide-spread research interest. The objectives of this research are to design and analyze self-stabilizing algorithms for maximal weight matching problem. Firstly, Hsu and Huang proved that the time complexity of their self-stabilizing algorithm for finding a maximal matching in distributed networks is O(n3), where n is the number of nodes in the graph. In 1994, Tel introduced a variant function to show that the time complexity of Hsu-Huang's algorithm is O(n2). In this paper, we design a self-stabilizing algorithm for maximal weight matching of the complete graph and prove its correctness. The maximal weight matching problem is defined not only to find the maximal matching of the complete graph, but also to let the total weight of the matching edges be maximal. We combine Hsu-Huang's maximal matching alogrithm and new swapping rules. This system possesses the properties of fault tolerance and self-stabilization and has a time complexity O(n2+nk), where k is the largest weight over all edges in the graph. en_US
dc.identifier 644D541A-7D31-6AF9-4A38-E34359DFB0B3 zh_TW
dc.identifier.uri http://rportal.lib.ntnu.edu.tw/handle/20.500.12235/17234
dc.language 中文 zh_TW
dc.publisher 國立臺灣師範大學研究發展處 zh_tw
dc.publisher Office of Research and Development en_US
dc.relation 45(1),21-36 zh_TW
dc.relation.ispartof 師大學報:數理與科技類 zh_tw
dc.subject.other 自我穩定演算法 zh_tw
dc.subject.other 系統容錯 zh_tw
dc.subject.other 最大配對問題 zh_tw
dc.subject.other 最大權重配對問題 zh_tw
dc.subject.other Self-stabilizing algorithm en_US
dc.subject.other Fault tolerance en_US
dc.subject.other Maximal matching problem en_US
dc.subject.other Maximal weight matching problem en_US
dc.title 完全圖上最大權重配對問題之自我穩定演算法的設計及分析 zh-tw
dc.title.alternative The Designs and Analyses of Self-Stabilizing Algorithm for Maximal Weight Matching Problem on Complete Graphs zh_tw
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
ntnulib_ja_L0803_0045_021.pdf
Size:
771.01 KB
Format:
Adobe Portable Document Format
Description:
Collections