Let G = (V, E) be a directed graph in which each vertex v has an integer label `

Question

Let G = (V, E) be a directed graph in which each vertex v has an integer label `(v) that denotes the influence of v. Assume for simplicity that all the influences are distinct. For each v V , let r(v) denote the vertex in G that has the largest influence among all vertices reachable from v in G. Design an algorithm that takes as input G, with the influence values `(v) for each v, and computes r(v) for each vertex v; that is, your algorithm should return the following set: {hv, r(v)i : v V }. Prove the correctness of your algorithm. Analyze its worst-case running time. The more efficient your algorithm is in terms of its asymptotic worst-case running time, the more credit you may get

Explanation / Answer

Algorithm:

The list will have maximum influence values for all vertices.

So by the above algorithm the worst case time complexity is the 2 loops which is of each n size. therefore it takes O(n2).

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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