Matching Theory - A Sampler: From Denes Koenig to the Present
Abstract
It was Koenig who gave the next strong impetus to the study of graph factorization after Petersen's ground breaking work, and it is Koenig with whom we are charged to begin out brief summary of the history of matching theory. Fortunately, matching theory serves well as an historical thread extending from the time of Koenig (and before) up to the present, wending its way through graph theory and intersecting many of the most important new ideas which have sprung forth in our discipline. One sees in particular that after the close of World War II this intertwining of matching theory with the study of graphs as a whole became ever more inextricable, even as the study of graph theory as a discipline unto itself literally exploded upon the mathematical scene. Although it is jumping the gun somewhat with respect to the organization of this paper, we can mention three major areas which have joined with graph theory to give rise to many new and deep results. These are: (1) linear programming and polyhydral combinatorics; (2) the linking of graphs and probability theory in the area of random graphs and finally (3) the theory of algorithms and computational complexity.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1991
- Accession Number
- ADA234321
Entities
People
- Michael D. Plummer
Organizations
- Vanderbilt University