Blocking flow: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 1: Line 1:
== Input ==
== Input ==


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

Revision as of 20:48, 19 October 2014

Input

  1. An acyclic directed graph [math]\displaystyle{ G=(V,A) }[/math].
  2. Source [math]\displaystyle{ s\in V }[/math] and target [math]\displaystyle{ t\in V }[/math].
  3. An upper boud [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