Dynamic Programming problem Well say that an edge in a conne

Dynamic Programming problem. We’ll say that an edge in a connected, undirected graph is bad if deleting that edge creates two connected components. Give a linear time algorithm to find all of the bad edges in a graph.

Be sure you define precisely what all the subproblems are, and give the recurrence for the optimal solution to each subproblem in terms of ”smaller” subproblems. Also provide pseudocode for the algorithm and a run-time analysis.

Solution

Below is the modified version of Tarjan\'s algorithm to find all the bridges in a graph. It takes O(V+E) time to execute. The basic idea is to use DFS traversal. We keep track of the parent node in an array parent[]. We also keep track of visited nodes, discovery time and lower time of nodes.

FindAllBridges(G, B)
   time = 0
   foreach vertex u E V
       visited[u] = FALSE
       parent[u] = NULL

    foreach vertex u E V
       if visited[u] == FALSE
           DFS(u)

DFS(u)
   visited[u] = TRUE
   discoveryTime[u] = lower[u] = ++time

   for each vertex v, adjacent to u
       if visited[v] is FALSE
           parent[v] = u
           DFS(v)                  
           lower[u] = Minimum(lower[u], lower[v])
           if discoveryTime[u] < lower[v]
               B <- B + edge(u,v) // it is a bridge, add it to the list
       otherwise if (v != parent[u])
           lower[u] = Minimum(lower[u], discoveryTime[v])