Matching Theory

L. Lovász and M.D. Plummer (Eds.)0444879161, 9780444879165, 9780080872322

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 of contents :
Content:
Edited by
Page C1

Copyright page
Page D1

Preface
Pages vii-xxvii

Basic Terminology
Pages xxix-xxxiii

1 Matchings in Bipartite Graphs
Pages 1-40

2 Flow Theory
Pages 41-81

3 Size and Structure of Maximum Matchings
Pages 83-119

4 Bipartite Graphs with Perfect Matchings
Pages 121-141

5 General Graphs with Perfect Matchings
Pages 143-211

6 Some Graph-theoretical Problems Related to Matchings
Pages 213-254

7 Matching and Linear Programming
Pages 255-305

8 Determinants and Matchings
Pages 307-355

9 Matching Algorithms
Pages 357-382

10 The f-factor Problem
Pages 383-408

11 Matroid Matching
Pages 409-441

12 Vertex Packing and Covering
Pages 443-482

References Review Article
Pages 483-526

Index of Terms
Pages 527-537

Index of Symbols
Pages 539-544