Titelaufnahme

Titel
A note on matchings constructed during Edmonds’ weighted perfect matching algorithm / Volker Kaibel and Matthias Walter
VerfasserKaibel, Volker ; Walter, Matthias
KörperschaftOtto-von-Guericke-Universität Magdeburg
Erschienen[Magdeburg] : [Otto-von-Guericke-Universität Magdeburg, Fakultät für Mathematik], March 29, 2017
Umfang1 Online-Ressource (8 ungezählte Seiten, 0,13 MB) : Illustrationen
Anmerkung
Unterschiede zwischen dem gedruckten Dokument und der elektronischen Ressource können nicht ausgeschlossen werden
SpracheEnglisch
SeriePreprints ; 2017, 06
URNurn:nbn:de:gbv:3:2-82322 
Zugriffsbeschränkung
 Das Dokument ist frei verfügbar
Dateien
A note on matchings constructed during Edmonds’ weighted perfect matching algorithm [0.12 mb]
Links
Nachweis
Kein Nachweis verfügbar
Klassifikation
Keywords
We reprove that all the matchings constructed during Edmonds’ weighted perfect matching algorithm are optimal among those of the same cardinality (provided that certain mild restrictions are obeyed on the choices the algorithm makes). We conclude that in order to solve a weighted matching problem it is not needed to solve a weighted perfect matching problem in an auxiliary graph of doubled size. This result was known before e.g. posed as an exercise in see Lawler’s book from 1976 but is not present in several modern books on combinatorial optimization.