Network Flow Problems - Stanford University

Network Flow ProblemsJaehyun ParkCS 97 SIStanford UniversityJune 29, 2015 OutlineNetwork Flow ProblemsFord-Fulkerson AlgorithmBipartite MatchingMin- cost Max-flow AlgorithmNetwork 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 bridgesNetwork Flow Problems3 Network Flow Problem Settings: Given a directed graphG= (V, E), where each edgeeis associated with its capacityc(e)>0. Two special nodessourcesand sinktare given(s6=t) Problem: Maximize the total amount of flow fromstotsubject to two constraints Flow on edgeedoesn t exceedc(e) For every nodev6=s, t, incoming flow is equal to outgoing flowNetwork 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 thatafter 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 )

Min-Cost Max-Flow A variant of the max-flow problem Each edge e has capacity c(e) and cost cost(e) You have to pay cost(e) amount of money per unit flow flowing through e Problem: find the maximum flow that has the minimum total cost A lot harder than the regular max-flow – But there is an easy algorithm that works for small graphs Min-cost Max-flow Algorithm 24

Loading..

Tags:

  Network, Cost, Flows, Minimum, Flow network, Cost cost

Information

Related search queries