There is a network of n nodes and diameter D. Suppose we have a set S of nodes.

Question

There is a network of n nodes and diameter D. Suppose we have a set S of nodes. The goal is to verify in a distributed manner if S is a maximal independent set (MIS). (a) Show that there exists an algorithm that terminates implicitly in time O(1) when S is a MIS. (b) Give an algorithm that terminates explicitly and estimate its time complexity. Your algorithm should rely only on the nodes having names but not on the knowl- edge of n or D. Hint: structure the termination phase of the algorithm as either computing a global AND or computing a global OR of boolean values.

Explanation / Answer

n Depth of a node v is equal to depth of the parent of v incremented by one.Therefore, our algorithm will mimic preorder traversal algorithm (each parent has to beprocessed" before its children). To compute depth of each node of T, the following algo-rithm should be called with T and T:root().Algorithm ComputeDepth (T, v):Input: tree T; v is a node of TOutput: depth of each node in the subtree of T rooted at vif (T.isRoot(v)) thensetDepth(v, 0)elsesetDepth(v, 1 + getDepth(T.parent(v)))children

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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