{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T05:45:44Z","timestamp":1698212744378},"reference-count":6,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":5558,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1992,1]]},"abstract":"Abstract<\/jats:title>This paper proposes a distributed algorithm for reconstructing a minimum\u2010weight spanning tree T<\/jats:italic>\u2032 of a network N<\/jats:italic>\u2032 when link addition and deletion occur in a network N<\/jats:italic> with a minimum\u2010weight spanning tree T.<\/jats:italic> In this algorithm each processor uses information whose adjacent links belong to T<\/jats:italic> in order to construct T<\/jats:italic>\u2032 efficiently. The communication complexity and ideal time complexity of the algorithm are O(n<\/jats:italic> log(f + t) + m)<\/jats:italic> and O(n<\/jats:italic> log(f + t) + n)<\/jats:italic>, respectively, where n<\/jats:italic> and e<\/jats:italic> are the number of processors and that of links in N<\/jats:italic>\u2032, t<\/jats:italic> is the number of added links, and f<\/jats:italic> represents that of deleted links belonging to T.<\/jats:italic> Here, m<\/jats:italic> = n<\/jats:italic> + t<\/jats:italic> when f<\/jats:italic> = 0 and m = e<\/jats:italic> otherwise.<\/jats:p>This paper also presents a distributed algorithm for reconstructing a minimum\u2010weight spanning tree T<\/jats:italic>+ when links and processors are added and deleted. The communication complexity and ideal time complexity of the algorithm are O(n<\/jats:italic> log(g + h) + r<\/jats:italic> and O(n<\/jats:italic> log(g + h)<\/jats:italic> + n)<\/jats:italic>, respectively, where g<\/jats:italic> is the total number of added links (including links incident to added processors) and h<\/jats:italic> represents the number of deleted links belonging to T<\/jats:italic> (including links incident to deleted processors). Thus, r = n + g<\/jats:italic> when h<\/jats:italic> = 0 and r = e<\/jats:italic> when h<\/jats:italic> > 0.<\/jats:p>","DOI":"10.1002\/scj.4690230301","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T23:31:49Z","timestamp":1183851109000},"page":"1-12","source":"Crossref","is-referenced-by-count":1,"title":["Efficient distributed algorithm to solve updating minimum spanning tree problem"],"prefix":"10.1002","volume":"23","author":[{"given":"Jungho","family":"Park","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ken'Ichi","family":"Hagihara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nobuki","family":"Tokura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshimitsu","family":"Masuzawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"C.Cheng I. A.Cimet andS. P.Kumar.A protocol to maintain a minimum spanning tree in a dynamic topology. Proc. of SIGCOMM '88 Symposium Communications Architectures and Protocols California pp.330\u2013337(1988).","DOI":"10.1145\/52325.52357"},{"key":"e_1_2_1_3_2","unstructured":"I. A.CimetandS. P.Kumar.A resilient distributed algorithm for minimum weight spanning trees. proc. 1987 International Conference on Parallel Processing pp.196\u2013203(1987)."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/357195.357200"},{"key":"e_1_2_1_5_2","first-page":"11","article-title":"On complexity of distributed algorithm","volume":"87","author":"Ken'ichi Hagihara","year":"1987","journal-title":"Proc. of The Logic Programming Conference"},{"key":"e_1_2_1_6_2","article-title":"On a distributed algorithm for constructing a minimum weight spanning tree\u2014The case of link deletion. Technical Report","volume":"89","author":"Park J.","year":"1989","journal-title":"I.E.I.C.E."},{"key":"e_1_2_1_7_2","unstructured":"Y. H.Tsin.An asynchronous distributed MST updating algorithm for handling vertex insertions in networks.Proc. Int. Conference on Parallel Processing and Applications (1987)."}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690230301","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690230301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T16:23:16Z","timestamp":1698164596000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690230301"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,1]]},"references-count":6,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,1]]}},"alternative-id":["10.1002\/scj.4690230301"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690230301","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,1]]}}}