This study of matching theory deals with bipartite matching, network flows, and presents fundamental results for the non-bipartite case. It goes on to study elementary bipartite graphs and elementary graphs in general. Further discussed are 2-matchings, general matching problems as linear programs, the Edmonds Matching Algorithm (and other algorithmic approaches), f-factors and vertex packing.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Chapter 2 Flow theory
Chapter 3 Size and structure of maximum matchings
Chapter 4 Bipartite graphs with perfect matchings
Chapter 5 General graphs with perfect matchings
Chapter 6 Some graphtheoretical problems related to matchings
Chapter 7 Matching and linear programming
Chapter 8 Determinants and matchings
Other editions - View all
1-extendable 2-matching 2-polymatroid adjacent assume bicritical graphs bigraph bipartite graph called characterization chromatic index Claim color combinatorial complete graph components of G Comput contradiction Corollary def(G defined denote ear decomposition Edmonds elementary bipartite graph elementary graph endpoints EXERCISE exists f-factor factor-critical graphs finite flow formulated G contains Gallai-Edmonds graph G graph theory hence hypergraph independent set inequalities integer joining König König's Theorem Lemma Let G linear programming lines of G Lovász Marriage Theorem matching algorithm matching in G matching of G matching polytope matching problem matching theory Math matrix matroid maximum matching minimal elementary Minimax Theorem non-bipartite non-negative NP-complete number of lines number of points obtain odd cycle partition path perfect graphs perfect matching planar graphs PM(G point cover points of G polynomial polytope prove result set of points spanning subgraph H subgraph of G submodular subset T-critical graph T-cuts T-join trivial