|
|
вернуться в форумПоказать все сообщения Спрятать все сообщенияhint svr 21 янв 2009 14:05 Using O(n^2) transitive closure in bipartite
Graph was successful. Does your solution use Hall's theorem? 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 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)) I said about complexity of submethod and
not about integral complexity.
i.e. about nonstandard part of algo. |
|
|
