Loading...
Please wait, while we are loading the content...
Similar Documents
Csc5160: Combinatorial Optimization and Approximation Algorithms Topic: General Matching 5.1 Min-max Theorem for General Matching
| Content Provider | Semantic Scholar |
|---|---|
| Author | Wu Jennifer X. M. |
| Copyright Year | 2008 |
| Abstract | We have considered matchings in bipartite graph, now we will consider matchings in general graph. Recall that a graph is bipartite if and only if it contains no odd cycles. Given a graph with weighted edges, the goal of the Maximum Matching problem is to find a matching (a set of vertex-disjoint edges) with maximum total weight. In this lecture, we focus on the cardinality version where the goal is to find a matching with the maximum number of edges. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://ion.uwinnipeg.ca/~ychen2/advancedAD/L05-matching.pdf |
| Alternate Webpage(s) | http://www.cse.cuhk.edu.hk/~chi/csc5160/notes/L05-matching.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |