Abstract: 3.1 Bipartite matchingIn the introductory chapters it turned out that finding a maximum cardinality matching in a bipartite graph plays a crucial role for assignment problems. Therefore, we discuss in this chapter various efficient methods for finding maximum matchings in bipartite graphs. Let G=(U,V;E) be a bipartite graph with vertex sets U={1,2,…,n} and V={1,2,…,s} and assume n≤s . The classical method uses simple labeling strategies for finding augmenting paths which finally lead to a maximum matching. This basic method has time complexity O(|U||E|).
Publication Year: 2012
Publication Date: 2012-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot