Question

An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. Give an efficient algorithm that finds a critical edge in a network

Short answer

The overall running time of the above algorithm is O(VE²)

Step-by-step solution

Introduction

Edge of network is having flow which is help to create some critically decreasing of maximum flow of connectivity. Even though an edges is critical towards the algorithm, it really should be completely filled.

Algorithm to find the critical edge in a network

Graph: G (V, E)

Output: FindCriticalEdge (G)

define getCriticalEdge (G):

residualGraph = fordFulkerson (G)

for edge u, v in residualGraph such that u, v is not in

residualGraph and u,v is not in

DFS ( residualGraph, u )

If has no path to v

Return u,v

return null

FordFulkerson Method

FordFulkerson approach is being used in the above procedure to obtain the maximum circulation inside a flow network. Even when an edge is crucial in the algorithm, it should have been filled to the brim; otherwise, the capacity will be reduced without compromising the maximum current.

All of this checks for a path from u to v using the DFS algorithm.

The for loop checks for the presence of something like a path every time DFS is run; if there isn't one, this edge seems to be a critical edge.

Therefore, the efficient algorithm to find the critical edge in a network has been obtained.