| dc.contributor | 資科系 | |
| dc.creator (作者) | Lien, Yao-nan | |
| dc.creator (作者) | 連耀南 | zh_TW |
| dc.date (日期) | 1988 | |
| dc.date.accessioned | 17-Jun-2015 16:42:18 (UTC+8) | - |
| dc.date.available | 17-Jun-2015 16:42:18 (UTC+8) | - |
| dc.date.issued (上傳時間) | 17-Jun-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 (資料類型) | conference | en |
| dc.identifier.doi (DOI) | 10.1109/DCS.1988.12534 | |
| dc.doi.uri (DOI) | http://dx.doi.org/10.1109/DCS.1988.12534 | |
