CSCI 570 - HW 8
1 Graded Problems
1. The edge connectivity of an undirected graph is the minimum number
of edges whose removal disconnects the graph. Describe an algorithm to
compute the edge connectivity of an undirected graph with n vertices and
m edges in O(m2n) time.
2. Solve Kleinberg and Tardos, Chapter 7, Exercise 7.
3. Solve Kleinberg and Tardos, Chapter 7, Exercise 9.
2 Practice Problems
1. An edge of a flow network G is called critical if decreasing the capacity
of this edge results in a decrease in the maximum flow. Is it true that
with respect to a maximum flow of G, any edge whose flow is equal to its
capacity is a critical edge? Give an efficient algorithm that finds a critical
edge in a flow network.
1
