{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T05:04:46Z","timestamp":1698037486867},"reference-count":5,"publisher":"Wiley","issue":"10","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":6653,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp;amp; Computers in Japan"],"published-print":{"date-parts":[[1989,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>When information data to solve a problem are distributed over processors on a network, the algorithm which solves the problem by exchanging the information data is called a distributed algorithm. A large number of distributed algorithms has been proposed for various problems, but the proof for the validity is shown only for a few of them. This paper considers an asynchronous network and proposes a distributed algorithm which constructs the breadth\u2010first search tree with the specified processor as the root. The validity of the algorithm is shown. In general, the efficiency of the distributed algorithm is evaluated by the total number of messages exchanged during execution (message complexity), and the execution time (ideal\u2010time complexity), assuming the communication delay as a unit time.<\/jats:p><jats:p>In the algorithm proposed in this paper, the message complexity and the ideal\u2010time complexity are both <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>\u00b7\u221a<jats:italic>e<\/jats:italic> where <jats:italic>n<\/jats:italic> is the number of processors and <jats:italic>e<\/jats:italic> is the number of links in the network. Especially, when <jats:italic>e<\/jats:italic> = <jats:italic>Q<\/jats:italic>((<jats:italic>n<\/jats:italic>\/log<jats:italic>n<\/jats:italic>)<jats:sup>2<\/jats:sup>), the proposed algorithm is better than other known algorithms in terms of the message complexity.<\/jats:p>","DOI":"10.1002\/scj.4690201002","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T16:50:37Z","timestamp":1183827037000},"page":"15-30","source":"Crossref","is-referenced-by-count":2,"title":["An efficient distributed algorithm for constructing a breadth\u2010first search tree"],"prefix":"10.1002","volume":"20","author":[{"given":"Jungho","family":"Park","sequence":"first","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"}]},{"given":"Ken'Ichi","family":"Hagihara","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":"B.AwerbuchandR. G.Gallager.Distributed BFS algorithms. Proc. of 26th FOCS (1985).","DOI":"10.1109\/SFCS.1985.20"},{"key":"e_1_2_1_3_2","unstructured":"G.Frederichson.A single shortest path algorithm for a planar distributed network. Proc. 2nd STACS (1985)."},{"key":"e_1_2_1_4_2","unstructured":"J.Park.An efficient distributed algorithm for constructing the breadth\u2010first search tree. Master's Thesis Fac. Eng. Sci. Osaka Univ. (1987)."},{"key":"e_1_2_1_5_2","article-title":"Distributed algorithm for constructing a breadth\u2010first search tree","volume":"86","author":"Park J.","year":"1986","journal-title":"I.E.C.E., Japan"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"R. G.Gallager.Distributed minimum hop algorithms. LIDS\u2010P\u20101175 (1982).","DOI":"10.21236\/ADA117808"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690201002","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690201002","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T13:40:54Z","timestamp":1697982054000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690201002"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,1]]},"references-count":5,"journal-issue":{"issue":"10","published-print":{"date-parts":[[1989,1]]}},"alternative-id":["10.1002\/scj.4690201002"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690201002","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,1]]}}}