CODEWITHSUNDEEP
algorithmnetwork-programminggraphmax-flow
John Smith
John Smith

Reputation: 633

Maximum flow bipartite with intermediate nodes

I'm working on a problem where one is to create a exam schedule based on some constraints by creating a flow network.

If a student is taking course c1 and c2, the two exams cannot be held at the same time.

I'm having trouble creating a flow network from these constraints. This is one of the networks I've tried to make so far. Flow Network

Black nodes are source and sink. Red are students. Green are courses. Orange are days. Blue are rooms.

The numbers represent the flow capacity.

After creating the appropriate flow graph, I know I would use the Ford-Fulkerson Algorithm to find the max flow.

Upvotes: 1

Views: 683

Answers (1)

tmyklebu
tmyklebu

Reputation: 14205

This isn't a flow problem. It's actually NP-complete; you can reduce the graph colouring problem to it as follows:

Take as the set of courses the vertex set of the graph in your graph colouring instance. For each edge in that graph, say between u and v, create a student who's taking only courses u and v. Have exactly as many time slots as there are colours available.

Then a feasible schedule (where no student has both of his exams at the same time) will be a colouring of your graph.

You might have better luck building an integer programming model of your problem.

Upvotes: 3

Related Questions