File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Improving the time complexity of message-optimal distributed algorithms for minimum-weight spanning trees

TitleImproving the time complexity of message-optimal distributed algorithms for minimum-weight spanning trees
Authors
Issue Date1990
PublisherSociety 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?
AbstractA 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 Identifierhttp://hdl.handle.net/10722/152228
ISSN
2015 Impact Factor: 0.841
2015 SCImago Journal Rankings: 1.808
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorChin, Fen_US
dc.contributor.authorTing, HFen_US
dc.date.accessioned2012-06-26T06:36:38Z-
dc.date.available2012-06-26T06:36:38Z-
dc.date.issued1990en_US
dc.identifier.citationSIAM Journal On Computing, 1990, v. 19 n. 4, p. 612-626en_US
dc.identifier.issn0097-5397en_US
dc.identifier.urihttp://hdl.handle.net/10722/152228-
dc.description.abstractA 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.languageengen_US
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SICOMPen_US
dc.relation.ispartofSIAM Journal on Computingen_US
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleImproving the time complexity of message-optimal distributed algorithms for minimum-weight spanning treesen_US
dc.typeArticleen_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.naturepublished_or_final_versionen_US
dc.identifier.doi10.1137/0219041-
dc.identifier.scopuseid_2-s2.0-0025474860en_US
dc.identifier.volume19en_US
dc.identifier.issue4en_US
dc.identifier.spage612en_US
dc.identifier.epage626en_US
dc.identifier.isiWOS:A1990DQ37900002-
dc.publisher.placeUnited Statesen_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