Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/0219041
- Scopus: eid_2-s2.0-0025474860
- WOS: WOS:A1990DQ37900002
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Improving the time complexity of message-optimal distributed algorithms for minimum-weight spanning trees
Title | Improving the time complexity of message-optimal distributed algorithms for minimum-weight spanning trees |
---|---|
Authors | |
Issue Date | 1990 |
Publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP |
Citation | SIAM Journal On Computing, 1990, v. 19 n. 4, p. 612-626 How to Cite? |
Abstract | A distributed algorithm is presented that constructs the minimum-weight spanning tree of an undirected connected graph with distinct node identities. Initially, each node knows only the weight of each of its adjacent edges. When the algorithm terminates, each node knows which of its adjacent edges are edges of the tree. For a graph with n nodes and e edges, the total number of messages required by this algorithm is at most 5n log n + 2e, where each message contains at most one edge weight plus 3 + log n bits. Although the algorithm presented here has the same message complexity as the previously known algorithm due to R.G. Gallager, P.A. Humblet, and P.M. Spira, the time complexity of the algorithm presented improves from Gallager's O(n log n) to O(n log n) time units, where log k is the number of times the log function must be applied to k to obtain a result less than or equal to one. A worst case of Ω(n log n) is also possible. In addition, when the network is synchronous, the algorithm presented is modified further to solve the same problem with the same message complexity but in O(n) time. |
Persistent Identifier | http://hdl.handle.net/10722/152228 |
ISSN | 2015 Impact Factor: 0.841 2015 SCImago Journal Rankings: 1.808 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chin, F | en_US |
dc.contributor.author | Ting, HF | en_US |
dc.date.accessioned | 2012-06-26T06:36:38Z | - |
dc.date.available | 2012-06-26T06:36:38Z | - |
dc.date.issued | 1990 | en_US |
dc.identifier.citation | SIAM Journal On Computing, 1990, v. 19 n. 4, p. 612-626 | en_US |
dc.identifier.issn | 0097-5397 | en_US |
dc.identifier.uri | http://hdl.handle.net/10722/152228 | - |
dc.description.abstract | A distributed algorithm is presented that constructs the minimum-weight spanning tree of an undirected connected graph with distinct node identities. Initially, each node knows only the weight of each of its adjacent edges. When the algorithm terminates, each node knows which of its adjacent edges are edges of the tree. For a graph with n nodes and e edges, the total number of messages required by this algorithm is at most 5n log n + 2e, where each message contains at most one edge weight plus 3 + log n bits. Although the algorithm presented here has the same message complexity as the previously known algorithm due to R.G. Gallager, P.A. Humblet, and P.M. Spira, the time complexity of the algorithm presented improves from Gallager's O(n log n) to O(n log n) time units, where log k is the number of times the log function must be applied to k to obtain a result less than or equal to one. A worst case of Ω(n log n) is also possible. In addition, when the network is synchronous, the algorithm presented is modified further to solve the same problem with the same message complexity but in O(n) time. | en_US |
dc.language | eng | en_US |
dc.publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP | en_US |
dc.relation.ispartof | SIAM Journal on Computing | en_US |
dc.rights | This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. | - |
dc.title | Improving the time complexity of message-optimal distributed algorithms for minimum-weight spanning trees | en_US |
dc.type | Article | en_US |
dc.identifier.email | Chin, F:chin@cs.hku.hk | en_US |
dc.identifier.email | Ting, HF:hfting@cs.hku.hk | en_US |
dc.identifier.authority | Chin, F=rp00105 | en_US |
dc.identifier.authority | Ting, HF=rp00177 | en_US |
dc.description.nature | published_or_final_version | en_US |
dc.identifier.doi | 10.1137/0219041 | - |
dc.identifier.scopus | eid_2-s2.0-0025474860 | en_US |
dc.identifier.volume | 19 | en_US |
dc.identifier.issue | 4 | en_US |
dc.identifier.spage | 612 | en_US |
dc.identifier.epage | 626 | en_US |
dc.identifier.isi | WOS:A1990DQ37900002 | - |
dc.publisher.place | United States | en_US |
dc.identifier.scopusauthorid | Chin, F=7005101915 | en_US |
dc.identifier.scopusauthorid | Ting, HF=7005654198 | en_US |