## Ford-Fulkerson Method

Facts

• The Ford-Fulkerson method $(G,S,t)$ is iterative
• This method depends on three ideas:
• Augmenting paths
• Residual networks
• Cuts
• Simplified Pseudo-code:
initialize flow f to 0
while there exist an augmenting path p
do augmented flow f along p
return f

Augmenting Paths

• An augmenting path $p$ is a simple path from source $S$ to sing $t$ in the residual network
• Each path have alternative free and matched edges in such way that begins and ends with free vertices.

Residual networks

• Definition: Each edge $(u,v)$ on an augmenting path admits some additional positive flow $u$ to $v$ without violating the capacity constrain on the edge.
• Example:

Cuts

Pseudocode

Ford-Fulkerson $(G,S,t)$
for each edge $(u,v)\epsilon&space;E[G]$
do $f[u,v]\leftarrow&space;0$ // $f$:flow
do $f[v,u]\leftarrow&space;0$
while there exist a path $p$ from $S$ to $t$ in the residual network $Gf$
do $cf(p)\leftarrow&space;min\{cf(u,v):&space;(u,v)$ is in $p&space;\}$ // $cf$: residual capacity
for each edge $(u,v)$ in $p$
do $f[u,v]\leftarrow&space;f[u,v]+cf(p)$ // $p$: path
do $f[v,u]\leftarrow&space;-f[u,v]$

Big O

Using either dept-first search or breadth-first search, the time to find a path in a residual network is $O(V+E$

Total running time is $O(E|F*|)$ where $f*$ is the maximum flow found

Note: If you find any mistake please let me know

## How to Create a Graph Derived from the 3-CNF Formula

The Clique Problem

The clique problem is an optimization problem where we ask if a clique (complete subgraphs) of a given size $k$ exists in the graph.
The idea is to find the clique maximum size in a graph.

List of Facts

• A clique in a undirected graph $G&space;=&space;(V,&space;E)$ is a subset $V$ of vertices
• Each pair of vertices is connected by an edge in $E$.
• A clique is a complete sub-graph of $G$
• The size of the clique is the number of vertices it contains

Example

Lets compute the graph from the formula $\phi$ in polynomial time.

• $\phi&space;=&space;(x_{1}&space;\vee&space;\neg&space;x_{2}&space;\vee&space;\neg&space;x_{3}&space;)&space;\wedge&space;(\neg&space;x_{1}&space;\vee&space;x_{2}&space;\vee&space;x_{3}&space;)&space;\wedge&space;(x_{1}&space;\vee&space;x_{2}&space;\vee&space;x_{3}&space;)$

Steps

First draw a graph $G$ derived from the formula $\phi$ where:

• $c_{1}&space;=&space;(x_{1}&space;\vee&space;\neg&space;x_{2}&space;\vee&space;\neg&space;x_{3}&space;)$
• $c_{2}&space;=&space;(\neg&space;x_{1}&space;\vee&space;x_{2}&space;\vee&space;x_{3}&space;)$
• $c_{3}&space;=&space;(x_{1}&space;\vee&space;x_{2}&space;\vee&space;x_{3}&space;)$
1. Connect $c_{1}(x_{1})$ to $c_{2}(x_{2},&space;x_{3})$ and $c_{3}(x_{1},x_{2},&space;x_{3})$
2. Connect $c_{1}(\neg&space;x_{2})$ to $c_{2}(\neg&space;x_{1},&space;x_{3})$ and $c_{3}(x_{1},&space;x_{3})$
3. Connect $c_{1}(\neg&space;x_{3})$ to $c_{2}(\neg&space;x_{1},&space;x_{2})$ and $c_{3}(x_{1},&space;x_{2})$
4. Connect $c_{2}(\neg&space;x_{1})$ to $c_{1}(x_{2},&space;x_{3})$
5. Connect $c_{2}(x_{2})$ to $c_{3}(x_{1},&space;x_{2},&space;x_{3})$
6. Connect $c_{2}(x_{3})$ to $c_{3}(x_{1},&space;x_{2},&space;x_{3})$
7. Done

## Maximum Flow

Definition

• The capacity constrain indicate that a given capacity must not be exceed by the flow from one vertex to another.
• The skew symmetry (a notational convenience) indicate that the flow from vertex $u$ to vertex $v$ is the negative of the flow in the reverse direction.
• The flow-conservation property indicate that the total flow out of a vertex other than the source $S$ or sink $t$ is 0
• The total positive flow leaving a vertex is defined symmetrically
• The total positive flow leaving the vertex minus the total positive flow entering a vertex is the  total net-flow at a vertex
• The total positive flow entering a vertex other than the source $S$ or sink $t$ must be equal to the positive flow leaving that vertex.

Examples

## Notes: Operative Systems – Part 6

NOTIFICATION: These notes are published for educational purposes. Using these notes is under your own responsibility and risk. These notes are given ‘as is’. I do not take responsibilities for how you use them.

PDF Content:

• Least recently used  (LRU) page replacement algorithm
• Not frequenty used (NFU) algorithm
• Aging (approximation of LRU) algorithm
• Working set
• Current virtual time
• Page replacement algorithm
• Clock page replacement algorithm
• WSClock page replacement algorithm
• Local vs. Global replacement policies
• Internal vs. External fragmentation
• Page size
• Periodic cleaning policy
• Thrashing
• Separation of policy and mechanism
• Concurrency vs. parallelism
• Critical sections