[PDF] CS 97SI 29-Jun-2015 Network Flow





Previous PDF Next PDF



Computer Networks

Types of Networks. » Network Devices. » Networking Topologies. » Identifying Nodes in a Networked. Communication. » Internet Web and the.



Federal Definitions for Health Insurance Products and Plans

27-Dec-2016 A product is a discrete package of health insurance coverage benefits that are offered using a particular product network type (such as ...



Basic Networking Concepts

-A network can be defined as a group of computers and other devices There are two principle kinds of networks: Wide Area Networks.



COMPUTER NETWORKS [R15A0513] LECTURE NOTES MALLA

Best example is the internet. Other types. WLAN (Wireless LAN). A LAN that uses high frequency radio waves for communication. Provides short range connectivity 



CS 97SI

29-Jun-2015 Network Flow Problem. ? A type of network optimization problem. ? Arise in many different contexts (CS 261):. – Networks: routing as many ...



Unit 1. Introduction to data communications and networking

This exchange of data takes place over a computer network. 1.2 DATA & INFORMATION Some of the forms of data used in communications are as follows:.



TYPES OF COMPUTER NETWORKS

Different Types of Networks. • Depending upon the geographical area covered by a network it is classified as: – Local Area Network (LAN).



EVOLUTION OF COMPUTER NETWORKS

The influence of computer networks on other types of telecommunications networks resulted in network convergence a process that started long before the 



CRYPTOGRAPHY AND NETWORK SECURITY LECTURE NOTES

Computer-based Symmetric Key Cryptographic Algorithms: Algorithm Types and Modes. An overview of Symmetric Key Cryptography



ATG - Storage PPT Template for 2021

•Deploying NVMe-0F IBM B-type switches. •ESG Paper -IBM FlashSystem with Brocade Gen 7. Storage Networking(SWITCHES) and Emulex. Fibre Channel Technology.



Networking Fundamentals - Cisco

Types of Networks Local Area Network (LAN) Metropolitan Area Network (MAN) Wide Area Network (WAN) © 2006 Cisco Systems Inc All rights reserved SMBUF-5 WAN Technologies Circuit-switched Asynchronous serial ISDN Layer 1 TELEPHONE COMPANY Leased Line Synchronous serial © 2006 Cisco Systems Inc All rights reserved SMBUF-6



Ppt of types of-network - SlideShare

Types of Networks Point to point vs Broadcast Circuit switched vs packet switched Local Area Networks (LAN) 0-2 km Metropolitan Area Networks (MAN) 2-50 km Wide Area Networks (WAN) 50+ km WAN Bus LAN Ring LAN The Ohio State UniversityRaj Jain 2- 6 Protocol Layers



TYPES OF COMPUTER NETWORKS - EazyNotes

TYPES OF COMPUTER NETWORKS The computers on a network may be linked through cables telephone lines radio waves satellites or infrared light beams Local Area Network (LAN) Metropolitan Area Network (MAN) Wide Area Network (WAN) Personal Area Network (PAN) A LAN is a network that is used for



Networking Basics - Class Presentation

Desirable 10 12 to 10 15 networks Raj Jain 27 IPv6 Addresses q 128-bit long Fixed size q 2128 = 3 4×10 38 addresses ? 665×10 21 addresses per sq m of earth surface

What are the devices used to connect network?

6. Devices Use To Connect Network: ? ? Routers ? Gateways ? Repeaters ? Bridges ? Hub ? Modem 6 7. Types Of Network: ? ? Local Area Network ? Wide Area Network ? Metropolitan Area Network 7 8.

What is a LAN network?

Local Area Network (LAN) Metropolitan Area Network (MAN) Wide Area Network (WAN) Personal Area Network (PAN) A LAN is a network that is used for communicating among computer devices, usually within an office building or home. LAN’s enable the sharing of resources such as files or hardware devices that may be needed by multiple users

What is a network and how does it work?

network consists of two or more computers that are linked in order to share resources (such as printers and CDs), exchange files, or allow electronic communications. The computers on a network may be linked through cables, telephone lines, radio waves, satellites, or infrared light beams. Local Area Network (LAN) Metropolitan Area Network (MAN)

What is a man network?

1. Is collection of LANs with the same geographical area, for instance a city. 2. Is a network of computers located at different sites within a large physical area, such as a city. 3. MAN often acts as a high speed network (although not as fast as LAN) to allow sharing of regional resources.

Network Flow Problems

Jaehyun Park

CS 97SI

Stanford University

June 29, 2015

Outline

Network Flow Problems

Ford-Fulkerson Algorithm

Bipartite Matching

Min-cost Max-flow Algorithm

Network Flow Problems2

Network Flow Problem

A type of network optimization problem

?Arise in many different contexts (CS 261): -Networks: routing as many packets as possible on a givennetwork

-Transportation: sending as many trucks as possible, whereroads have limits on the number of trucks per unit time

-Bridges: destroying (?!) some bridges to disconnectsfromt, while minimizing the cost of destroying the bridges

Network Flow Problems3

Network Flow Problem

Settings: Given a directed graphG= (V,E), where each edge eis associated with its capacityc(e)>0. Two special nodes sourcesand sinktare given(s?=t) ?Problem: Maximize the total amount of flow fromstot subject to two constraints -Flow on edgeedoesn"t exceedc(e) -For every nodev?=s,t, incoming flow is equal to outgoing flow

Network Flow Problems4

Network Flow Example (from CLRS)

Capacities

?Maximum flow (of 23 total units)

Network Flow Problems5

Alternate Formulation: Minimum Cut

We want to remove some edges from the graph such that after removing the edges, there is no path fromstot ?The cost of removingeis equal to its capacityc(e) ?The minimum cut problem is to find a cut with minimumtotal cost ?Theorem:(maximum flow) = (minimum cut) ?Take CS 261 if you want to see the proof

Network Flow Problems6

Minimum Cut Example

Capacities

?Minimum Cut (red edges are removed)

Network Flow Problems7

Flow Decomposition

Any valid flow can be decomposed into flow paths and circulations -s→a→b→t: 11 -s→c→a→b→t: 1 -s→c→d→b→t: 7 -s→c→d→t: 4

Network Flow Problems8

Outline

Network Flow Problems

Ford-Fulkerson Algorithm

Bipartite Matching

Min-cost Max-flow Algorithm

Ford-Fulkerson Algorithm9

Ford-Fulkerson Algorithm

A simple and practical max-flow algorithm

?Main idea: find valid flow paths until there is none left, andadd them up ?How do we know if this gives a maximum flow? -Proof sketch: Suppose not. Take a maximum flowf?and "subtract" our flowf. It is a valid flow of positive total flow. By the flow decomposition, it can be decomposed into flow paths and circulations. These flow paths must have been found by Ford-Fulkerson. Contradiction.

Ford-Fulkerson Algorithm10

Back Edges

We don"t need to maintain the amount of flow on each edge but work with capacity values directly ?Iffamount of flow goes throughu→v, then: -Decreasec(u→v)byf -Increasec(v→u)byf ?Why do we need to do this? -Sending flow to both directions is equivalent to canceling flow

Ford-Fulkerson Algorithm11

Ford-Fulkerson Pseudocode

Setftotal= 0

?Repeat until there is no path fromstot: -Run DFS fromsto find a flow path tot -Letfbe the minimum capacity value on the path -Addftoftotal -For each edgeu→von the path: ?Decreasec(u→v)byf ?Increasec(v→u)byf

Ford-Fulkerson Algorithm12

Analysis

Assumption: capacities are integer-valued

?Finding a flow path takesΘ(n+m)time ?We send at least 1 unit of flow through the path ?If the max-flow isf?, the time complexity isO((n+m)f?) -"Bad" in that it depends on the output of the algorithm -Nonetheless, easy to code and works well in practice

Ford-Fulkerson Algorithm13

Computing Min-Cut

We know that max-flow is equal to min-cut

?And we now know how to find the max-flow ?Question: how do we find the min-cut? ?Answer: use the residual graph

Ford-Fulkerson Algorithm14

Computing Min-Cut

"Subtract" the max-flow from the original graph

Ford-Fulkerson Algorithm15

Computing Min-Cut

Mark all nodes reachable froms

-Call the set of reachable nodesA ?Now separate these nodes from the others -Cut edges going fromAtoV-A

Ford-Fulkerson Algorithm16

Computing Min-Cut

Look at the original graph and find the cut:

?Why isn"tb→ccut?

Ford-Fulkerson Algorithm17

Outline

Network Flow Problems

Ford-Fulkerson Algorithm

Bipartite Matching

Min-cost Max-flow Algorithm

Bipartite Matching18

Bipartite Matching

Settings:

-nstudents andddorms -Each student wants to live in one of the dorms of his choice -Each dorm can accommodate at most one student (?!) ?Fine, we will fix this later... ?Problem: find an assignment that maximizes the number ofstudents who get a housing

Bipartite Matching19

Flow Network Construction

Add source and sink

?Make edges between students and dorms -All the edge weights are 1

Bipartite Matching20

Flow Network Construction

Find the max-flow

?Find the optimal assignment from the chosen edges

Bipartite Matching21

Related Problems

A more reasonable variant of the previous problem: dormj can accommodatecjstudents -Make an edge with capacitycjfrom dormjto the sink ?Decomposing a DAG into nonintersecting paths -Split each vertexvintovleftandvright -For each edgeu→vin the DAG, make an edge fromuleftto v right ?And many others...

Bipartite Matching22

Outline

Network Flow Problems

Ford-Fulkerson Algorithm

Bipartite Matching

Min-cost Max-flow Algorithm

Min-cost Max-flow Algorithm23

Min-Cost Max-Flow

A variant of the max-flow problem

?Each edgeehas capacityc(e)and costcost(e) ?You have to paycost(e)amount of money per unit flow flowing throughe ?Problem: find the maximum flow that has the minimum totalcost ?A lot harder than the regular max-flow -But there is an easy algorithm that works for small graphs

Min-cost Max-flow Algorithm24

Simple (?) Min-Cost Max-Flow

Forget about the costs and just find a max-flow

?Repeat: -Take the residual graph -Find a negative-cost cycle using Bellman-Ford ?If there is none, finish -Circulate flow through the cycle to decrease the total cost,until one of the edges is saturated ?The total amount of flow doesn"t change! ?Time complexity: very slow

Min-cost Max-flow Algorithm25

Notes on Max-Flow Problems

Remember different formulations of the max-flow problem -Again,(maximum flow) = (minimum cut)! ?Often the crucial part is to construct the flow network ?We didn"t cover fast max-flow algorithms -Refer to the Stanford Team notebook for efficient flowalgorithms

Min-cost Max-flow Algorithm26

quotesdbs_dbs19.pdfusesText_25
[PDF] types of operators pdf

[PDF] types of oral presentation

[PDF] types of organizational structure

[PDF] types of phrases in english

[PDF] types of phrases in english grammar examples

[PDF] types of phrases in english grammar exercises

[PDF] types of phrases in english grammar pdf

[PDF] types of phrases in english grammar ppt

[PDF] types of phrases in english pdf

[PDF] types of phrases in english syntax

[PDF] types of phrases ppt

[PDF] types of priority scheduling

[PDF] types of probability pdf

[PDF] types of programming language

[PDF] types of programming languages