1
$\begingroup$

I am working out with the rooks problem. If there are m rooks on an nxn chessboard,i have to give describe a polynomial (in m and n) time algorithm that finds a maximum-sized subset of the rooks such that if we leave this subset on the chessboard and remove all other rooks, then no two rooks attack one another. (Two rooks are said to attack one another if and only if they are either in the same row or in the same column with no other intervening rooks between them.)

My idea for solving this problem is to consider a bipartite graph (X,Y) where X is the rows in the chessboard and Y is the columns. if a row and column have a rook placed at their intersection, then there is an edge between the those vertices from x to y. This can be converted into a maximum flow network and the value of max flow is the max matching.

In order to find a polynomial time algorithm i can run maybe BFS.

I wanted to know that if i build my solution on this idea shall it be correct. Is there a better algorithm (polynomial in m and n)?

Any help is appreciated.

Improve this question
$\endgroup$
1
  • $\begingroup$ When i convert the maximum bipartite graph to a flow network, the edges are directed and weighted. All the edges are assigned capacities 1, also source and sink are added and edge between source s and x has capacity infinite. So it would be a directed weighted graph at the end, and i have to find the maximum flow in the netwrok. $\endgroup$
    – user1325120
    Commented Mar 20, 2014 at 16:26

1 Answer 1

Reset to default
2
$\begingroup$

As you mention, your problem is finding a maximum matching in an unweighted bipartite graph. There are several polynomial time algorithms for solving this problem. You can read about some of them on the Wikipedia page.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.