Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading about maximum flows in Introduction to algorithms by Cormen etc.

Ford-Fulkerson algorithm is given below.

FORD-FULKERSON(G, s, t)

1  for each edge (u, v) in E[G]

2       do â[u, v]  0

3          â[v, u]  0

4  while there exists a path p from s to t in the residual network Gâ

5      do câ(p)  min {câ(u, v) : (u, v) is in p}

6         for each edge (u, v) in p

7             do â[u, v]  â[u, v]+câ(p)

8                â[v, u]  - â[u, v]

While analyzing above algorithm author is mentioned as below.

The work done within the while loop can be made efficient if we efficiently manage the data structure used to implement the network G = (V, E). Let us assume that we keep a data structure corresponding to a directed graph G' = (V, E'), where E' = {(u, v) : (u, v) belong to E or (v, u) belongs to E}. Edges in the network G are also edges in G', and it is therefore a simple matter to maintain capacities and flows in this data structure. Given a flow â on G, the edges in the residual network Gâ consist of all edges (u, v) of G' such that c(u, v) - â[u, v] not equal to 0. The time to find a path in a residual network is therefore O(E') = O(E) if we use either depth-first search or breadth-first search. Each iteration of the while loop thus takes O(E) time, making the total running time of FORD-FULKERSON O(E | â* |).

My questions on above text.

  1. Can any one please explain above paragraph easy to understand? I think both G and G' is same structually what differnce it makes?
  2. What does author mean by "dges in the network G are also edges in G', and it is therefore a simple matter to maintain capacities and flows in this data structure." ?
  3. How author came with The time to find a path in a residual network is therefore O(E') = O(E) if we use DFS or BFS?

Thanks for your time and help.

share|improve this question

migrated from stackoverflow.com Jun 6 '12 at 13:01

This question came from our site for professional and enthusiast programmers.

2 Answers 2

There's not a heck of a lot of context here, but let's see if I can try to help:

  1. Regarding the set E' - if (a,b) is in E, then both (a,b) and (b,a) will be in E', which is why G is not the same as G'.

  2. It means it in the sense that there are representative edges in G' for every edge in G, I assume.

  3. I think this is just a structural property based on the fact that the edges of G' are a superset of the edges of G. Without more context I'm really not sure what's going on here.

share|improve this answer
    
No, if (a,b) is in E, then both (a,b) and (b,a) are in E'. In particular, E' is always a superset of E. On the other hand, $|E'| \le 2|E|$, so $O(E') = O(E)$. –  JeffE Jun 9 '12 at 15:17
    
Whoops! I should have read more carefully. Thanks for the correction. –  Gian Jun 11 '12 at 15:36

1) $G$ and $G'$ are both directed graphs. The edges in $G'$ either coincide with those of $G$ or reverse them. This also answers the second question - lines 7-8 maintain flow conservation and skew-symmetry by sending $\hat{a} [u,v]$ along the reverse edge after each forward edge has $c\overline{a}(p)$ added to it. For three, the augmenting path found in line $4$ is equivalent to the search problem in a graph - using Depth or Breadth - First Search, the runtime of this operation is $O(E).$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.