Consider a ring network R where entities are anonymous (i.e., they do not have a

Question

Consider a ring network R where entities are anonymous (i.e., they do not have an id). Each link has an integer associated to it called cost (known to both entities connected by it). All links have different costs. The cost of a spanning-tree T of R is the sum of the costs of all the edges in T. Consider the problem of finding the minimum cost spanning tree. Assuming that there is message ordering (FIFO assumption), design an algorithm to solve the problem as efficiently as possible and analyze its message complexity. As usual, do not make any additional assumption, and refrain from using messages that are too large (a message should contain only a constant number of values).

Explanation / Answer

For this problem we can use the ghs algorithm to solve the minimum spanning algorithm. It basically assigns a level to each fragment with initial value set to zero. Now the edges in the graph are divided into three categories as branch edges, rejected edges and basic edges.

Based on the distinction we can divide the problem and can get the solution for minimum spanning algorithm.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.