
Accession Number : ADA183908
Title : Some Recent Results on Graph Matching,
Corporate Author : VANDERBILT UNIV NASHVILLE TN DEPT OF MATHEMATICS
Personal Author(s) : Lavasz, Laszlo ; Plummer, Michael D
PDF Url : ADA183908
Report Date : Jun 1987
Pagination or Media Count : 17
Abstract : A matching in a graph G is a set of lines, no two of which share a common point. A matching is perfect if it spans V(G). The problem of finding a matching of maximum cardinality in a graph models a number of significant realworld problems and, in addition, is of considerable mathematical interest in its own right. Matchings are in a sense among the best understood graphtheoretic objects: there exist efficient algorithms to find and good characterizations for the existence of perfect matchings and for the maximum weight of a matching; there are nice descriptions of polyhedra associated with matchings; good bounds and, for a few special classes, exact formulas for the number of perfect matchings in a graph. But there are many important questions that remain unanswered. What is the number of perfect matchings in a general graph? Which graphs can be written as the disjoint union of perfect matchings (i.e., which rregular graphs are rlinecolorable)? How does one generate a random perfect matching? Matching theory has often been in the front lines of research in graph theory and many results in matching theory have served as pilot results for new branches of study in combinatorics (e.g., minimax theorems, good characterizations and polyhedral descriptions).
Descriptors : *GRAPHS, *THEOREMS, ALGORITHMS, EFFICIENCY, GRAPHS, MATCHING, MODELS, THEORY, WEIGHT
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE