Transcription of Network Flow Problems - Stanford University
{{id}} {{{paragraph}}}
Example: air traffic controller
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.
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 flow algorithms Min-cost Max-flow Algorithm 26
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: