Distributed minimum spanning tree: Difference between revisions

Content deleted Content added

Revision as of 19:47, 30 December 2024 edit 189.156.187.30 (talk) No edit summary Tags: Reverted Mobile edit Mobile web edit ← Previous edit		Latest revision as of 19:50, 30 December 2024 edit undo Nyxion303 (talk \| contribs) Extended confirmed users 8,457 edits Reverted 1 edit by 189.156.187.30 (talk): Rv; removed with no reason Tags: Twinkle Undo
(4 intermediate revisions by 2 users not shown)
Line 1: ~~trees~~[[Image:Minimum spanning tree.svg\|thumb\|400px\|right\|''Example of a MST:'' The minimum spanning tree of a [[planar graph]]. Each edge is labeled with its weight, which here is roughly proportional to its length.]] 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 (computing)\|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.