File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/SFCS.1985.7
- Scopus: eid_2-s2.0-0022204522
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: ALMOST LINEAR TIME AND O(N LOG N plus E) MESSAGES DISTRIBUTED ALGORITHM FOR MINIMUM-WEIGHT SPANNING TREES.
| Title | ALMOST LINEAR TIME AND O(N LOG N plus E) MESSAGES DISTRIBUTED ALGORITHM FOR MINIMUM-WEIGHT SPANNING TREES. |
|---|---|
| Authors | |
| Issue Date | 1985 |
| Citation | Annual Symposium On Foundations Of Computer Science (Proceedings), 1985, p. 257-266 How to Cite? |
| Abstract | A distributed algorithm is presented that constructs the minimum-weight spanning tree of an undirected connected graph with distinct edge weights and 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 the algorithm is at most 5n log n plus 2e, and each message contains at most one edge weight or one node identity plus 3 plus log n bits. The time complexity is at most O(nG(n)) plus time units. A worst-case O(nG(n)) is also possible. |
| Persistent Identifier | http://hdl.handle.net/10722/151783 |
| ISSN | 2020 SCImago Journal Rankings: 2.949 |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Chin, F | en_US |
| dc.contributor.author | Ting, HF | en_US |
| dc.date.accessioned | 2012-06-26T06:29:30Z | - |
| dc.date.available | 2012-06-26T06:29:30Z | - |
| dc.date.issued | 1985 | en_US |
| dc.identifier.citation | Annual Symposium On Foundations Of Computer Science (Proceedings), 1985, p. 257-266 | en_US |
| dc.identifier.issn | 0272-5428 | en_US |
| dc.identifier.uri | http://hdl.handle.net/10722/151783 | - |
| dc.description.abstract | A distributed algorithm is presented that constructs the minimum-weight spanning tree of an undirected connected graph with distinct edge weights and 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 the algorithm is at most 5n log n plus 2e, and each message contains at most one edge weight or one node identity plus 3 plus log n bits. The time complexity is at most O(nG(n)) plus time units. A worst-case O(nG(n)) is also possible. | en_US |
| dc.language | eng | en_US |
| dc.relation.ispartof | Annual Symposium on Foundations of Computer Science (Proceedings) | en_US |
| dc.title | ALMOST LINEAR TIME AND O(N LOG N plus E) MESSAGES DISTRIBUTED ALGORITHM FOR MINIMUM-WEIGHT SPANNING TREES. | en_US |
| dc.type | Conference_Paper | 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 | link_to_subscribed_fulltext | en_US |
| dc.identifier.doi | 10.1109/SFCS.1985.7 | en_US |
| dc.identifier.scopus | eid_2-s2.0-0022204522 | en_US |
| dc.identifier.spage | 257 | en_US |
| dc.identifier.epage | 266 | en_US |
| dc.identifier.scopusauthorid | Chin, F=7005101915 | en_US |
| dc.identifier.scopusauthorid | Ting, HF=7005654198 | en_US |
| dc.identifier.issnl | 0272-5428 | - |