.png){kind=icon}
Return
An efficient distributed algorithm for constructing a breadth‐first search tree
.png){kind=icon}
PRE
AI
DOI：10.1002/scj.4690201002.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
AbstractWhen 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‐first 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‐time complexity), assuming the communication delay as a unit time.In the algorithm proposed in this paper, the message complexity and the ideal‐time complexity are both O(n·√e where n is the number of processors and e is the number of links in the network. Especially, when e = Q((n/logn)2), the proposed algorithm is better than other known algorithms in terms of the message complexity.
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
No journal information available
Organization
No organization information available
Cited Papers
No cited papers available