Hmmm.. Interesting Just in case someone does want to use BFS and does not really care about the time complexity, then you could do BFS to get all the Paths ( do not remove them as soon as you get them ) For example in the graph in the previous discussion, BFS would give S37F, S345F and S267F now we would have to find out the cardinality of the maximum maximal set of disjoint paths from the set obtained. In this case this would be 2 for the set S345F and S267F so we would get the result. The complexity would now be O(k(n^3+mn^2)(n+m)^2)
On 4/25/06, forest <[EMAIL PROTECTED]> wrote: > > there is an example of BFS fail: > - - - 2 ---- 6 - - - -- 7 - - - - - > S / -- - - - - - / F > - - - 3- - - - 4 - -- - - 5 - -- - - - > > going form S to F. k = 2. BFS finds path S37F, as it is shortest. > After removing this path there is no other path from S to F. But > choosing paths another way you could get 2. > > > > About restrictions on vertexes - it is rather well known trick. You > double each vertex and get 2 vertexes V' and V''. Make all the graph > directed. There is an edge from V' to V'' with capacity equal to > vertex initial capacity. All in-edges come to V' all out-edges go from > V''. > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
