MatchingAlgorithmus

Ein Matching-Algorithmus bezeichnet in der Graphentheorie einen Algorithmus zur Bestimmung eines Matchings, also einer Menge von Kanten, bei der keine zwei Kanten gemeinsame Endpunkte haben. Ein Matching modelliert Zuordnungen zwischen Objekten in einem Graphen. Typische Varianten hängen von der Struktur des Graphen ab: ungerichtete allgemeine Graphen oder bipartite Graphen und von der Frage, ob das Matching ungewichtete oder gewichtete Kanten berücksichtigt.

Im bipartiten Fall zielt man oft darauf ab, ein möglichst großes Matching oder ein perfektes Matching zu finden. Bekannte Algorithmen sind der Kuhn-Algorithmus (DFS-basiert), der Hopcroft–Karp-Algorithmus mit Laufzeit O(E√V) sowie Umsetzungen über Flussnetze (Ford–Fulkerson). Für gewichtete bipartite Zuordnungen existiert der Hungarian-Algorithmus mit typischer Komplexität O(n^3). In allgemeinen Graphen liefert der Edmonds–Blossom-Algorithmus das maximale Matching, mit zeitlicher Komplexität in der Größenordnung O(V^3) in gängigen Implementierungen.

Gewichtete, minimal-cost- oder maximal-gewichtete Zuordnungen fallen unter die Kategorie Weighted Matching, wobei Algorithmen wie der Gabow-Tarjan-Algorithmus oder Variation des Hungarian-Algorithmus verwendet werden. Ein weiteres wichtiges Konzept ist das stabile Matching, wie im Gale–Shapley-Verfahren, das stabile Paarungen zwischen zwei Gruppen garantiert, ohne notwendigerweise ein maximales Cardinality-Matching zu liefern.

Anwendungen finden sich in der Personal- oder Ressourcenallokation, in der Zuweisung von Aufgaben, im Netzwerkdesign oder in Marktplätzen und Matching-Portalen. Praktisch wird oft die passende Datenstruktur gewählt (Adjazenzlisten, Flussdarstellungen) und die Wahl des Algorithmus an Größe und Gewichtung angepasst.