1. NCCU Academic Hub
  2. 學術產出
  3. 資訊學院
  4. 會議論文
  5. Item

學術產出-會議論文

文章檢視/開啟

書目匯出

Google ScholarTM

政大圖書館

引文資訊

TAIR相關學術產出

題名 A New Node-Join-Tree Distributed Algorithm for Minimum Weight Spanning Trees
作者 Lien, Yao-nan
連耀南
貢獻者 資科系
日期 1988
上傳時間 17-六月-2015 16:42:18 (UTC+8)
摘要 A distributed algorithm that uses a node-join-tree approach for the minimum-spanning-tree problem in a communication network is developed. The algorithm needs at most (2e+n(n-1)/4) messages in O(n2 ) time on a general random graph. In the best case, it needs only 2e messages in O(log n) time. The parameters e and n are the number of edges and nodes, respectively. Although the worst-case performance is not better than that of tree-join-tree algorithms under some extreme cases, simulation results show that it provides better performance in most cases. The algorithm is initialized from a single node, so that there is no need to wake up all nodes at the beginning. It is less complicated than other algorithms, so that a reliable implementation is easier to achieve. The results can be used to improve the algorithms for many other problems in distributed computing, such as leader-election, node-counting, deadlock-resolution, and message-broadcasting
關聯 International Conference on Distributed Computing Systems - ICDCS , pp. 334-340
資料類型 conference
DOI http://dx.doi.org/10.1109/DCS.1988.12534
dc.contributor 資科系
dc.creator (作者) Lien, Yao-nan
dc.creator (作者) 連耀南zh_TW
dc.date (日期) 1988
dc.date.accessioned 17-六月-2015 16:42:18 (UTC+8)-
dc.date.available 17-六月-2015 16:42:18 (UTC+8)-
dc.date.issued (上傳時間) 17-六月-2015 16:42:18 (UTC+8)-
dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/75914-
dc.description.abstract (摘要) A distributed algorithm that uses a node-join-tree approach for the minimum-spanning-tree problem in a communication network is developed. The algorithm needs at most (2e+n(n-1)/4) messages in O(n2 ) time on a general random graph. In the best case, it needs only 2e messages in O(log n) time. The parameters e and n are the number of edges and nodes, respectively. Although the worst-case performance is not better than that of tree-join-tree algorithms under some extreme cases, simulation results show that it provides better performance in most cases. The algorithm is initialized from a single node, so that there is no need to wake up all nodes at the beginning. It is less complicated than other algorithms, so that a reliable implementation is easier to achieve. The results can be used to improve the algorithms for many other problems in distributed computing, such as leader-election, node-counting, deadlock-resolution, and message-broadcasting
dc.format.extent 128 bytes-
dc.format.mimetype text/html-
dc.relation (關聯) International Conference on Distributed Computing Systems - ICDCS , pp. 334-340
dc.title (題名) A New Node-Join-Tree Distributed Algorithm for Minimum Weight Spanning Trees
dc.type (資料類型) conferenceen
dc.identifier.doi (DOI) 10.1109/DCS.1988.12534
dc.doi.uri (DOI) http://dx.doi.org/10.1109/DCS.1988.12534