of course the time complexity could be substantially reduced using the flow model of the problem.l\
On 4/26/06, Karthik Singaram L <[EMAIL PROTECTED]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
