The following question involves maximum flowalgorithms, namely Ford- Fulkerson andEdmonds-Karp.
Just do question 2.1 below. The yellow and green partsare hints. Explain the answer only using words, numbers and/orpseudocode.
The Following Question Involves Maximum Flow Algorithms Namely Ford Fulkerson And Edmonds Karp Just Do Question 2 1 B 1 (83.33 KiB) Viewed 35 times
There are k people living in a city, whose n suburbs and m roads can be represented by an unweighted directed graph. Every person is either slow or fast. Every night, • Each slow person can stay in the same suburb, or move along a road to an adjacent suburb. • Each fast person can stay in the same suburb, or move to any other suburb in the entire city. Over the last d days, you know how many people were located in each suburb. That is, for each day i and suburb j (where 1 ≤ i ≤ d and 1 ≤j≤n), you know pij, the number of people located in suburb j on day i. You are guaranteed that - Pij = k for all i. 2.1 [10 marks] Design an algorithm which runs in O(d(n + m)) time and determines whether there could possibly be at least one slow person. Start with small cases such as d = 2, and then generalise. 2.2 [10 marks] Design an algorithm which runs in time polynomial in n, m, and d, and deter- mines the minimum possible number of fast people. • Has the wording in the third paragraph changed? Yes. This problem was updated on 03/07/22. • If there is no path from suburb i to suburb j, can a fast person move between them? Yes. Fast people essentially teleport.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!