JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Network flow algorithm? | Reply
Hi,

I have got a problem like this:

We are given a bipartite graph. For e.g.

A1 B1
A2 B2
A3 B3
A4

And here is the adjacency list representation (assume graph is bidirectional)

B1 -> A2, A3
B2 -> A2, A3, A4
B3 -> A1

Final result should be that all nodes in the left side (As) have exactly 1 incoming edge and at the same time - we need to minimize the maximum number of edges that need to go out of individual Bs nodes. In this case the answer would be:

B3 can connect to A1
B2 can connect to A2, A4
B1 can connect to A3

So here the maximum number of edges that need to out of a single Bs node is 2. We cannot cover all As and at the same time have a B node not having 2 edges going out of it to cover As.

Another example:

A1 B1
A2 B2
A3 B3
A4 B4

B1 -> A1, A2, A3
B2 -> A1, A2, A3, A4
B3 -> A1, A2, A3
B4 -> A1, A2, A3

In this case the answer would be:

B1 can connect to A1
B2 can connect to A4
B3 can connect to A3
B2 can connect to A2

This way we will cover all the As exactly once and at the same time we have minimized the maximum number of edges that need to go out of individual B's. So here the maximum number of edges that need to out of a single Bs node is 1.

Another example:

A1 B1
A2 B2
A3 B3
A4
A5
A6

B1 -> A6
B2 -> A1, A2, A3, A4, A5
B3 ->

In this case the answer would be 5 i.e. the maximum number of edges that need to go out of a single Bs is 5. Can't do less than that.

I have implemented basic ford fulkerson algorithm and I know this is also network flow but don't know how to relate to it.

It will be great if someone can give some hint about the graph.

Thanks
Re: Network flow algorithm? (response to post by vsha041) | Reply
Well I found it anyway - It can be done by having a source node connected to all A's and connecting all B's to a sink node. Then give the edge weight of 1 to all nodes from source to A's - find the max flow - if its not equal to maximum of A's that can be covered - increase those edge capacities by 1 - keep doing till you reach the maximum of A's that can be covered. Push - Relabel will give (number of A's that be covered) * n^3 performance which is quite fast.
RSS