Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Recent Progress in Matching Extension
verfasst von : Michael D. Plummer
Erschienen in: Building Bridges
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
G
be a graph with at least 2
n
+2 vertices, where n is a no
n
-negative integer. The graph
G
is said to be
n-extendable
if every matching of size
n
in
G
extends to (i.e., is a subset of) a perfect matching. The study of this concept began in earnest in the 1980’s, although it was born out of the study of canonical matching decompositions carried out in the 1970’s and before. As is often the case, in retrospect it is apparent that there are roots of this topic to be found even earlier.
In the present paper, we will begin with a brief history of the subject and then concentrate on reviewing results on n-extendability and closely related areas obtained in the last ten-fifteen years, as there already exist two surveys of the subject in 1994 and 1996, respectively.