Suppose you are given a directed graph G = (V, E), with positive integer capacit

Question

Suppose you are given a directed graph G = (V, E), with positive integer capacity c_e on each edge e. You are also given a set of sources s_1. ....., s_n and a set of sinks t_1, ..., t_m. Each source s_i has a supply of up to S_i amount of flow that can be sent out from it, and each sink t_j has a demand D_j for flow that it receives. Design a polynomial time algorithm to determine whether it is possible to design a flow that meets all demands of all sinks subject to the supplies of the sources.

Explanation / Answer

Yes, it's possible to design a polynomial time algorithm to meet all demands and supplies.
Attach a new sink SINK' with edges of capacity dj = demand j from each sink j, to this SINK'. ->atleast dj flows from each sink (demand)
Attach a new source SOUCE' with edges of capacity si = supply max to each souce i, from SOUCE' -> max si flows to source. (supply)

Now, use ford fulkerson algorithm -> polynomial time algorithm to find the max flow. If the max flow equals sum of all demands on the sinks then a flow exists, otherwise not.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.