1
1.
2. 3.
2
1.
CSCI 570 – Spring 2018 – HW 8
Due October 28st 11:59pm 2020
Graded Problems
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.
Solve Kleinberg and Tardos, Chapter 7, Exercise 7. Solve Kleinberg and Tardos, Chapter 7, Exercise 9.
Practice Problems
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