Distributed minimum spanning tree
The distributed minimum spanning tree (MST) problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles Borůvka's algorithm. One important application of this problem is to find a tree that can be used for broadcasting. In particular, if the cost for a message to pass through an edge in a graph is significant, an MST can minimize the total cost for a source process to communicate with all the other processes in the network.
- Comment
- enThe distributed minimum spanning tree (MST) problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles Borůvka's algorithm. One important application of this problem is to find a tree that can be used for broadcasting. In particular, if the cost for a message to pass through an edge in a graph is significant, an MST can minimize the total cost for a source process to communicate with all the other processes in the network.
- Depiction
- Has abstract
- enThe distributed minimum spanning tree (MST) problem involves the construction of a minimum spanning tree by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles Borůvka's algorithm. One important application of this problem is to find a tree that can be used for broadcasting. In particular, if the cost for a message to pass through an edge in a graph is significant, an MST can minimize the total cost for a source process to communicate with all the other processes in the network. The problem was first suggested and solved in time in 1983 by Gallager et al., where is the number of vertices in the graph. Later, the solution was improved to and finally where D is the network, or graph diameter. A lower bound on the time complexity of the solution has been eventually shown to be
- Is primary topic of
- Distributed minimum spanning tree
- Label
- enDistributed minimum spanning tree
- Link from a Wikipage to another Wikipage
- Borůvka's algorithm
- Broadcasting (computing)
- Category:Distributed algorithms
- Category:Spanning tree
- Distributed algorithm
- Distributed computing
- FIFO (computing and electronics)
- File:Minimum spanning tree.svg
- Graph theory
- Kruskal's algorithm
- Message passing
- Minimum spanning tree
- Prim's algorithm
- Robert G. Gallager
- SameAs
- 4imrq
- Distributed minimum spanning tree
- m.0fvln9
- Q5283163
- درخت پوشای مینیمم توزیع شده
- Subject
- Category:Distributed algorithms
- Category:Spanning tree
- Thumbnail
- WasDerivedFrom
- Distributed minimum spanning tree?oldid=1123786407&ns=0
- WikiPageLength
- 15496
- Wikipage page ID
- 6183392
- Wikipage revision ID
- 1123786407
