JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Maximum Flow tutorial Some mistakes
 Some mistakes | Reply I've found some small mistakes with the figures in the article.In Section 1:...Let's color in yellow, like in the figure above, every vertex that is reachable by a path that starts from the source and consists of non-full forward edges and of non-empty backward edges...Shouldn't it be like in the figure below?In Section 2:...Now suppose we add 1 to the capacity of each edge. Is a minimum cut in the original network a minimum cut in this one? The answer is no, as we can see in Figure 8 shown below, if we take T = 2.Shouldn't it be Figure 9?Regarding to the article, I would like to know why are there at most N*M/2 steps in the max flow algorithm when using BFS to find augmenting paths, how can it be proved?Thanks in advance :)
 Subject Author Date Some mistakes roypalacios Sep 20, 2008 at 6:55 PM EDT
 Forums Tutorial Discussions Maximum Flow tutorial Some mistakes Previous Thread  |  Next Thread