A commander is located at one node p in a network. His subordinates constitute a

Question

A commander is located at one node p in a network. His subordinates constitute a node set S. The enemy needs to cut off the communication between the commander and his subordinates (commander should not be able to communicate to any of his subordinates). Enemy needs w(e) effort to remove an edge e in the network. The goal is to compute the minimum effort required to cut off the communication between the commander and his subordinates. (a) Propose a polynomial-time algorithm for the special case when there is only one subordinate, i.e., S = {q} is a singleton. (b) Propose a polynomial-time algorithm for the general case.

Explanation / Answer

a) mark commander as source, and S = {q} as sink. Using the max-flow min-cut algorithm, we can use the ford-fulkerson algorithm to find the max flow of the network, this runs in polynomial time. Since, the max flow = min cut, this would be the result.
b) create a new sink, and join all subordinates to this sink with edge value equal to all incoming edges to the vertices. The max flow would give the min cut of this network, and hence the result.

Ford fulkerson terminates on integral capacities, and runs in polynomial time.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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