Given a set of buyers, houses, agents with the following constraints: Agents onl

Question

Given a set of buyers, houses, agents with the following constraints:

Agents only know a subset of buyers
Agents only know a subset of houses
Agents can only do some amount of transactions

Construct a flow network to model the problem. Disclaimer this is homework

I have put together some thoughts on a solution to this problem. First I realized that agents should be right before the sink node with a max flow equal to the number of possible transactions. This would then limit the number of transactions that can flow through an agent since the max flow can't be exceeded.

I was then thinking that it would be possible to put an edge between each person and house that an agent knows (example if agent knows person A, B and house 1, 2 there are edges (A,1), (A,2), (B,1), (B,2)). Finally, connect each house that an agent knows to an agent with max flow of 1. Then by running a Ford-Fulkerson algorithm across it the inflow of the sink node would indicate max number of transactions.

However, I am concerned that there is no limit of stopping a house from being purchased more than once. I have tried building the network with various configurations (swapping houses and clients, building nodes of client/house pairs) and nothing seems to solve this specific problem.

I am mostly looking for hints to solve this problem.

Explanation / Answer

Hint: think about your source node and what it is connected to.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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