Details

Autor(en) / Beteiligte

• Lovász, László,
• Plummer, M. D

Titel

Matching theory [electronic resource]

Link zum Volltext

• Elsevier Books AutoHoldings

Beschreibungen/Notizen

• Description based upon print version of record.
• Includes bibliography and indexes.
• Front Cover; Matching Theory; Copyright Page; Table of Contents; Preface; Basic Terminology; Chapter 1. Matchings in bipartite graphs; 1.0. Introduction; 1.1. The Theorems of Konig, P. Hall and Frobenius; 1.2. A bipartite matching algorithm: the Hungarian Method; 1.3. Deficiency, surplus and a glimpse of matroid theory; 1.4. Some consequences of bipartite matching theorems; Chapter 2. Flow theory; 2.0. Introduction; 2.1. The Max-Flow Min-Cut Theorem; 2.2. Flow algorithms; 2.3. Flow-equivalent trees; 2.4. Applications of flow theory to matching theory; 2.5. Matchings, flows and measures
• Chapter 3. Size and structure of maximum matchings3.0. Introduction; 3.1. Tutte's theorem, Gallai's lemma and Berge's formula; 3.2. The Gallai-Edmonds Structure Theorem; 3.3. Toward a calculus of barriers; 3.4. Sufficient conditions for matchings of a given size; Chapter 4. Bipartite graphs with perfect matchings; 4.0. Introduction; 4.1. Elementary graphs and their ear structure; 4.2. Minimal elementary bipartite graphs; 4.3. Decomposition into elementary bipartite graphs; Chapter 5. General graphs with perfect matchings; 5.0. Introduction; 5.1. Elementary graphs: elementary properties
• 5.2. The canonical partition P(G)5.3. Saturated graphs and cathedrals; 5.4. Ear structure of 1-extendable graphs; 5.5. More about factor-critical and bicritical graphs; Chapter 6. Some graph-theoretical problems related to matchings; 6.0. Introduction; 6.1. 2-matchings and 2-covers; 6.2. 2-bicritical and regularizable graphs; 6.3. Matchings, 2-matchings and the Konig Property; 6.4. Hamilton cycles and 2-matchings; 6.5. The Chinese Postman Problem; 6.6. Optimum paths, cycles, joins and cuts; Chapter 7. Matching and linear programming; 7.0. Introduction
• 7.1. Linear programming and matching in bigraphs7.2. Matchings and fractional matchings; 7.3. The matching polytope; 7.4. Chromatic index; 7.5. Fractional matching polytopes and cover polyhedra; 7.6. The dimension of the perfect matching polytope; Chapter 8. Determinants and matchings; 8.0. Introduction; 8.1. Permanents; 8.2. The method of variables; 8.3. The Pfaffian and the number of perfect matchings; 8.4. Probabilistic enumeration of perfect matchings; 8.5. Matching polynomials; 8.6. More on the number of perfect matchings; 8.7. Two applications to physical science
• Chapter 9. Matching algorithms9.0. Introduction; 9.1. The Edmonds Matching Algorithm; 9.2. Weighted matching; 9.3. An algorithm based upon the Gallai-Edmonds Theorem; 9.4. A linear programming algorithm for matching; Chapter 10. The f-factor problem; 10.0. Introduction; 10.1. Reduction principles; 10.2. A structure theory for f -factors; 10.3. Realization of degree sequences; Chapter 11. Matroid matching; 11.0. Introduction; 11.1. Formulations of the Matroid Matching Problem; 11.2. The main theorem of polymatroid matching; 11.3. Matching in special polymatroids
• Chapter 12. Vertex packing and covering
• 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.
• English