Blocking flow: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 9: Line 9:
== Input ==
== Input ==


# An [[Basic graph definitions|acyclic]] directed graph <math>G=(V,A)</math>.
# An [[Basic graph definitions#Cycles|acyclic]] directed graph <math>G=(V,A)</math>.
# Source <math>s\in V</math> and target <math>t\in V</math>.
# A source node <math>s\in V</math> and a target node <math>t\in V</math>.
# An upper boud <math>u(a)</math> for each arc <math>a\in A</math>.
# An upper bound <math>u(a)</math> for each arc <math>a\in A</math>.


== Output ==
== Output ==

Revision as of 19:03, 9 November 2014

Definition

Let [math]\displaystyle{ G=(V,A) }[/math] be a directed graph, let [math]\displaystyle{ s,t\in V }[/math], and for each arc [math]\displaystyle{ a\in A }[/math] let [math]\displaystyle{ u(a) }[/math] and [math]\displaystyle{ f(a) }[/math] be real values such that [math]\displaystyle{ 0\leq f(a)\leq u(a) }[/math]. We say that [math]\displaystyle{ f }[/math] is a blocking flow if every flow augmenting [math]\displaystyle{ (s,t) }[/math]-path contains at least one backward arc.

Remarks:

  1. The name refers to an alternative, equivalent definition: Every ordinary [math]\displaystyle{ (s,t) }[/math]-path contains at least one saturated arc, which "blocks" the augmentation.
  2. Obviously, maximum flows are blocking flows, but not vice versa.

Input

  1. An acyclic directed graph [math]\displaystyle{ G=(V,A) }[/math].
  2. A source node [math]\displaystyle{ s\in V }[/math] and a target node [math]\displaystyle{ t\in V }[/math].
  3. An upper bound [math]\displaystyle{ u(a) }[/math] for each arc [math]\displaystyle{ a\in A }[/math].

Output

A blocking flow [math]\displaystyle{ f }[/math].

Known Algorithms

  1. Blocking flow by Dinic
  2. Three indians' algorithm