|
|
back to boardhint Posted by svr 21 Jan 2009 14:05 Using O(n^2) transitive closure in bipartite Graph was successful. Re: hint Posted by Al.Cash 26 Jan 2009 21:30 Does your solution use Hall's theorem? Re: hint Posted by svr 26 Jan 2009 21:57 May be. If it is Hall's. Now it is mine:edge (ra,rb) can precence in some assigment solution if and only if 1)it's begining ra achievable by alternating path's with respect to some given matching from it's end rb. OR 2) Some free vertex achievable from rb. Edited by author 26.01.2009 22:01 Re: hint Posted by Al.Cash 28 Jan 2009 01:10 Your statement is quite simple to prove and it seems very useful for this problem. But don't you need to build some matching before applying it? Then the algorithm's complexity is O(N^2*M), which is much slower then O(N^2) mentioned before)) Re: hint Posted by svr 28 Jan 2009 09:26 I said about complexity of submethod and not about integral complexity. i.e. about nonstandard part of algo. |
|
|