CODEWITHSUNDEEP
algorithmgraphtime-complexitygraph-theory
JohnMat
JohnMat

Reputation: 3

Time complexity of custom graph flow algorithm

I need to know what's the complexity of the following graph algorithm and how did you manage to find it:

R = (G, s, t, c) be transportation network such that

Consider the following recursive function where A(u) is the list of out-neighbors of vertex u and initially x is the null flow.

 Flow(u, α)
   if ((v ← next[A(u)]) == NULL) then
      return α;
   flowOut ← 0;
   for ((v ← next[A(u)]) 6= NULL) do
      if (α > 0) then
         x[uv] ← Flow(v, min {c[uv], α});
         flowOut ← flowOut + x[uv];
         α ← α − x[uv];
      else
         break;
   return flowOut;

Also is this graph a known one so I can search more about it on the internet? Thank you!

Upvotes: 0

Views: 121

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65506

It's basically DFS, so linear time. It reminds me of algorithms that compute a blocking flow.

Upvotes: 1

Related Questions