- Given a graph with integer capacities on its edges, and two special vertices critical edge of is an edge with the property that increasing its capacity would increase the value of the maximum flow. Give an efficient algorithm to identify all critical edges of a graph.
- Let be an undirected graph with capacities on each edge . Let be two of its vertices. Let be the set of paths in and be the subsets of edges that are cuts. Show that .
- Given an undirected graph with non-negative integer capacities on edges, give an efficient algorithm to find the global min-cut, i.e., the smallest capacity set of edges whose removal disconnects the graph.
- Let be a directed graph with capacities on its edges and two special vertices . The capacity of a directed path from to is the smallest of the capacities of edges on the path. Give an efficient algorithm to find a path from to of maximum capacity.

Advertisements