Transcription of CMSC 451: Maximum Bipartite Matching
{{id}} {{{paragraph}}}
Example: bankruptcy
CMSC 451: Maximum Bipartite Matching
CMSC 451: Maximum Bipartite MatchingSlides By: carl KingsfordDepartment of Computer ScienceUniversity of Maryland, College ParkBased on Section ofAlgorithm Designby Kleinberg & Flowssuvtxw201030205301020101051515510 The network flow problem is itself even more interesting is how you can use it to solve manyproblems that don t involve flows or even Graphs Suppose we have a set ofpeopleLand set of jobsR. Each person can do onlysome of the jobs. Can model this as abipartite graph uxLRPeopleTasksPerson u can do task xBipartite Matching Amatchinggives anassignment of people totasks. Want to get as many tasksdone as possible. So, want amaximummatching: one thatcontains as many edges aspossible. (This one is not Maximum .)abcde12345 LRPeopleTasksMaximum Bipartite MatchingMaximum Bipartite MatchingGiven a Bipartite graphG= (A B,E), find anS A Bthat isa Matching and is as large as : We re givenAandBso we don t have to find them.
Slides By: Carl Kingsford Department of Computer Science University of Maryland, College Park Based on Section 7.5 of Algorithm Design by Kleinberg & Tardos. Network Flows s u v t x w 20 10 30 20 5 30 10 20 10 10 5 15 15 5 10 The network ow problem is itself interesting. But even more interesting is how you can use it to solve many
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: