Universitšt Oldenburg
Fachbereich Informatik

Publications: Details


Document Description

Author: Günther Stiege
Title: Flowerfree Finding of Maximum Matchings
Kind of Publication: Report. Berichte aus dem Department für Informatik 02/12, Universität Oldenburg, June 2012
Date: June 2012
Institution: Universitšt Oldenburg; Graphen und Netzwerke
Pages, Language 8 English
Keywords: Maximum matching
CR Classification: E.1 [Data structures] (Graphs and networks)
General Terms (ACM): Algorithms
up

Abstract

Actual algorithms for finding maximum matchings are based on Edmonds' techniques of shrinking and expnding cirduits of odd length (blossoms and flowers). Here a new approach based on modified alternatings depth-first search is presented. It uses coupled recursion.

Kurzfassung

Derzeitige Algorithmen zum Finden maximaler Korrespondenzen basieren aud Edmonds' Techniken zum Schrumpfen und Expandieren von Kreisen ungerader Länge (Blüten und Blumen). Hier wird eine neue Lösung mit einer modifizierten alternierenden Tiefensuche vorgestellt. Sie benutzt gekoppelte Rekursion.

up

Download

up

Remarks

None.
up


Last change: 2007/06/17 (Stiege)