COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Matching Theory - 1st Edition - ISBN: 9780444879165, 9780080872322

Matching Theory, Volume 29

1st Edition

Authors: M.D. Plummer L. Lovász
eBook ISBN: 9780080872322
Imprint: North Holland
Published Date: 1st June 1986
Page Count: 543
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.

Table of Contents

1. Matchings in Bipartite Graphs. Introduction. The Theorems of König, P. Hall and Frobenius. A Bipartite Matching Algorithm: The Hungarian Method. Deficiency, Surplus and a Glimpse of Matroid Theory. Some Consequences of Bipartite Matching Theorems. 2. Flow Theory. Introduction. The Max-Flow Min-Cut Theorem. Flow Algorithms. Flow-Equivalent Trees. Applications of Flow Theory to Matching Theory. Matchings, Flows and Measures. 3. Size and Structure of Maximum Matchings. Introduction. Tutte's Theorem, Gallai's Lemma and Berge's Formula. The Gallai-Edmonds Structure Theorem. Towards a Calculus of Barriers. Sufficient Conditions for Matchings of a Given Size. 4. Bipartite Graphs with Perfect Matchings. Introduction. Elementary Graphs and their Ear Structure. Minimal Elementary Bipartite Graphs. Decomposition into Elementary Bipartite Graphs. 5. General Graphs with Perfect Matchings. Introduction. Elementary Graphs: Elementary Properties. The Canonical Partition P(G). Saturated Graphs and Cathedrals. Ear Structure of 1-Extendable Graphs. More About Factor-Critical and Bicritical Graphs. 6. Some Graph-Theoretical Problems Related to Matchings. Introduction. 2-Matchings and 2-Covers. 2-Bicritical and Regularizable Graphs. Matchings, 2-Matchings and the König Property. Hamilton Cycles and 2-Matchings. The Chinese Postman Problem. Optimum Paths, Cycles, Joins and Cuts. 7. Matching and Linear Programming. Introduction. Linear Programming and Matching in Bigraphs. Matchings and Fractional Matchings. The Matching Polytope. Chromatic Index. Fractional Matching Polytopes and Cover Polyhedra. The Dimension of the Perfect Matching Polytope. 8. Determinants and Matchings. Introduction. Permanents. The Method of Variables. The Pfaffian and the Number of Perfect Matchings. Probabilistic Enumeration of Perfect Matchings. Matching Polynomials. More on the Number of Perfect Matchings. Two Applications to Physical Science. 9. Matching Algorithms. Introduction. The Edmonds Matching Algorithm. Weighted Matching. An Algorithm based upon the Gallai-Edmonds Theorem. A Linear Programming Algorithm for Matching. 10. The f-Factor Problem. Introduction. Reduction Principles. A Structure Theory for f-Factors. Realization of Degree Sequences. 11. Matroid Matching. Introduction. Formulations of the Matroid Matching Problem. The Main Theorem of Polymatroid Matching. Matching in Special Polymatroids. 12. Vertex Packing and Covering. Introduction. Critical Graphs. Vertex Packing Polytopes. Hypergraph Matching. Vertex Packing in Claw-Free Graphs. References. Indices.


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.


No. of pages:
© North Holland 1986
1st June 1986
North Holland
eBook ISBN:


@qu:It begins at an elementary level and ends at the frontiers of current research, and the journey is enlivened by readable exposition, helpful motivation, interesting historical background and elegant proofs... a truly notable achievement...
@source:Bulletin of the London Mathematical Society
@qu:Everything is developed with splendid clarity, organized in a masterful way and written in an excellent style, sometimes exciting, sometimes humorous, always maintaining a lively dialogue with the reader. This beautiful book provides a comprehensive treatment of the subject, leading up to the frontiers of current research.

Ratings and Reviews

About the Authors

M.D. Plummer

L. Lovász

Affiliations and Expertise

Princeton University, Department of Computer Science, USA