## Ford-Fulkerson Method

Facts

• The Ford-Fulkerson method  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 is a simple path from source to sing in the residual network
• Each path have alternative free and matched edges in such way that begins and ends with free vertices.

Residual networks

Cuts

Pseudocode

Ford-Fulkerson
for each edge
do // :flow
do
while there exist a path from to in the residual network
do is in // : residual capacity
for each edge in
do // : path
do

Big O

Using either dept-first search or breadth-first search, the time to find a path in a residual network is

Total running time is where 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  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  is a subset  of vertices
• Each pair of vertices is connected by an edge in .
• A clique is a complete sub-graph of
• The size of the clique is the number of vertices it contains

Example

Lets compute the graph from the formula in polynomial time.

Steps

First draw a graph  derived from the formula where:

1. Connect to and
2. Connect  to  and
3. Connect  to  and
4. Connect  to
5. Connect  to
6. Connect  to
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 to vertex 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 or sink 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 or sink 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