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

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.