Blocking flow: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Input == # A directed graph <math>G=(V,A)</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<...") |
No edit summary |
||
| (6 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Basic definitions == | |||
# [[Basic graph definitions]] | |||
# [[Basic flow definitions]] | |||
== Definition == | |||
Let <math>G=(V,A)</math> be a directed graph, let <math>s,t\in V</math>, and for each arc <math>a\in A</math> let <math>u(a)</math> and <math>f(a)</math> be real values such that <math>0\leq f(a)\leq u(a)</math>. We say that <math>f</math> is a '''blocking flow''' if every flow augmenting <math>(s,t)</math>-path contains at least one backward arc. | |||
'''Remarks:''' | |||
# The name refers to an alternative, equivalent definition: Every ordinary <math>(s,t)</math>-path contains at least one saturated arc, which "blocks" the augmentation. | |||
# Obviously, maximum flows are blocking flows, but not vice versa. | |||
== Input == | == Input == | ||
# | # An [[Basic graph definitions#Cycles|acyclic]] [[Basic graph definitions#Directed and undirected graphs|directed graph]] <math>G=(V,A)</math>. | ||
# | # A source node <math>s\in V</math> and a target node <math>t\in V</math>. | ||
# An upper | # An upper bound <math>u(a)</math> for each arc <math>a\in A</math>. | ||
== Output == | == Output == | ||
A | A blocking flow <math>f</math>. | ||
== Known Algorithms == | |||
# [[Blocking flow by Dinic]] | |||
# [[Three indians' algorithm]] | |||
Latest revision as of 19:06, 9 November 2014
Basic definitions
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:
- 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.
- Obviously, maximum flows are blocking flows, but not vice versa.
Input
- An acyclic directed graph [math]\displaystyle{ G=(V,A) }[/math].
- A source node [math]\displaystyle{ s\in V }[/math] and a target node [math]\displaystyle{ t\in V }[/math].
- 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].