Consider the condensation of a directed graph G(V, E), GSCC(V', E'). In GSCC, each strongly connected...

Transcribed Image Text:

Consider the condensation of a directed graph G(V, E), GSCC(V', E'). In GSCC, each strongly connected component of G is represented by a single vertex. Let C(u) for u E V' denote the vertices in the strongly connected component represented by u (C(u) ≤ V). We add a directed edge (u, v) to GSCC if and only if there is some edge (u', v') E E where u' E C(u) and v' E C(v). (i) Give an algorithm which, given a directed graph G(V, E) returns the condensation, GSCC. You can assume that you already have a connectivity labeling of the vertices, i.e., a labeling L such that L(u) = L(v) if and only if u and v are in the same strongly connected component. Your algorithm to compute the condensation of G should run in O(m + n) time. (ii) Suppose you are given an arbitrary directed graph G where each vertex has exactly one out-neighbor. Give an algorithm that runs in O(m + n) time to compute the minimum number of edges to add to make G strongly connected. Consider the condensation of a directed graph G(V, E), GSCC(V', E'). In GSCC, each strongly connected component of G is represented by a single vertex. Let C(u) for u E V' denote the vertices in the strongly connected component represented by u (C(u) ≤ V). We add a directed edge (u, v) to GSCC if and only if there is some edge (u', v') E E where u' E C(u) and v' E C(v). (i) Give an algorithm which, given a directed graph G(V, E) returns the condensation, GSCC. You can assume that you already have a connectivity labeling of the vertices, i.e., a labeling L such that L(u) = L(v) if and only if u and v are in the same strongly connected component. Your algorithm to compute the condensation of G should run in O(m + n) time. (ii) Suppose you are given an arbitrary directed graph G where each vertex has exactly one out-neighbor. Give an algorithm that runs in O(m + n) time to compute the minimum number of edges to add to make G strongly connected.

Answer rating: 100% (QA)

i Algorithm to compute the condensation of a directed graph GVE 1 Intialize an empty graph GSCCV E where V contains one vertex for each strongly conne... View the full answer