The following question involves maximum flowalgorithms, namely Ford- Fulkerson andEdmonds-Karp.
Just do question 4.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 4 1 B 1 (93.82 KiB) Viewed 64 times
You are given a flow network G with n vertices, including a sources and sink t, and m directed edges with integer capacities. Your friend will ask you several queries of the form: "If an edge were to be added to G, going from vertex a to vertex b with capacity c, what would the maximum flow of the modified network be?" Note that each query considers adding an edge to the original flow network, so the modified network has m + 1 edges. Before asking any queries, your friend gives you some time to prepare, which you can spend on precomputation. Design an algorithm which performs any required precomputation and then answers each query in constant time, subject to the following restrictions: 4.1 [5 marks] O(nm²) precomputation; b = t and c = 1 in all queries. How would the new edge have changed how the Ford-Fulkerson algorithm proceeded? 4.2 [6 marks] O(nm²) precomputation; c= 1 in all queries. 4.3 [7 marks] O(n²m²) precomputation; b = t in all queries. 4.4 [2 marks] O(n²m²) precomputation; queries unrestricted. Can I skip 4.1 and/or 4.3? Yes. You may choose to skip 4.1, in which case we will mark your submission for 4.2 as if it was submitted for 4.1 also. Likewise, if you skip 4.3 then we will mark your submission for 4.4 as if it was submitted for 4.3 also.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!