Matching TheoryElsevier, 1 juin 1986 - 543 pages 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. |
Table des matières
| 1 | |
Chapter 2 Flow theory | 41 |
Chapter 3 Size and structure of maximum matchings | 83 |
Chapter 4 Bipartite graphs with perfect matchings | 121 |
Chapter 5 General graphs with perfect matchings | 143 |
Chapter 6 Some graphtheoretical problems related to matchings | 213 |
Chapter 7 Matching and linear programming | 255 |
Chapter 8 Determinants and matchings | 307 |
Chapter 9 Matching algorithms | 357 |
Chapter 10 The ffactor problem | 383 |
Chapter 11 Matroid matching | 409 |
Chapter 12 Vertex packing and covering | 443 |
References | 483 |
| 527 | |
| 539 | |
Autres éditions - Tout afficher
Expressions et termes fréquents
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