Accession Number:

ADA234321

Title:

Matching Theory - A Sampler: From Denes Koenig to the Present

Descriptive Note:

Corporate Author:

VANDERBILT UNIV NASHVILLE TN DEPT OF MATHEMATICS

Personal Author(s):

Report Date:

1991-01-01

Pagination or Media Count:

47.0

Abstract:

It was Koenig who gave the next strong impetus to the study of graph factorization after Petersens 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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE