File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: ALMOST LINEAR TIME AND O(N LOG N plus E) MESSAGES DISTRIBUTED ALGORITHM FOR MINIMUM-WEIGHT SPANNING TREES.

TitleALMOST LINEAR TIME AND O(N LOG N plus E) MESSAGES DISTRIBUTED ALGORITHM FOR MINIMUM-WEIGHT SPANNING TREES.
Authors
Issue Date1985
Citation
Annual Symposium On Foundations Of Computer Science (Proceedings), 1985, p. 257-266 How to Cite?
AbstractA 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 Identifierhttp://hdl.handle.net/10722/151783
ISSN

 

DC FieldValueLanguage
dc.contributor.authorChin, Fen_US
dc.contributor.authorTing, HFen_US
dc.date.accessioned2012-06-26T06:29:30Z-
dc.date.available2012-06-26T06:29:30Z-
dc.date.issued1985en_US
dc.identifier.citationAnnual Symposium On Foundations Of Computer Science (Proceedings), 1985, p. 257-266en_US
dc.identifier.issn0272-5428en_US
dc.identifier.urihttp://hdl.handle.net/10722/151783-
dc.description.abstractA 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.languageengen_US
dc.relation.ispartofAnnual Symposium on Foundations of Computer Science (Proceedings)en_US
dc.titleALMOST LINEAR TIME AND O(N LOG N plus E) MESSAGES DISTRIBUTED ALGORITHM FOR MINIMUM-WEIGHT SPANNING TREES.en_US
dc.typeConference_Paperen_US
dc.identifier.emailChin, F:chin@cs.hku.hken_US
dc.identifier.emailTing, HF:hfting@cs.hku.hken_US
dc.identifier.authorityChin, F=rp00105en_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1109/SFCS.1985.7en_US
dc.identifier.scopuseid_2-s2.0-0022204522en_US
dc.identifier.spage257en_US
dc.identifier.epage266en_US
dc.identifier.scopusauthoridChin, F=7005101915en_US
dc.identifier.scopusauthoridTing, HF=7005654198en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats