Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


34. Paarung



Weiterentwickelte Algorithmen

Die beiden Spezialfälle, die wir betrachtet haben, geben eine Vorstellung von der Schwierigkeit des Paarungsproblems. Obwohl diese speziellen Algorithmen für verschiedene reale Anwendungen der angegebenen Art von Nutzen sind, können viele andere Anwendungen die Lösung von allgemeineren Problemen erfordern.

Zu den allgemeineren Problemen, die gründlicher untersucht worden sind, gehören: das Problem der maximalen Paarung für allgemeine (nicht notwendig bipartite) Graphen; gewichtete Paarung für bipartite Graphen, wobei Kanten Gewichte haben und eine Paarung mit maximalem Gesamtgewicht gesucht wird; sowie gewichtete Paarung für allgemeine Graphen.

Gewichtete Paarung für bipartite Graphen und ähnliche Verallgemeinerungen können in dem Umfang verarbeitet werden, in dem Algorithmen für Verallgemeinerungen des Problems des Flusses in einem Netzwerk bekannt sind. Allgemeine Graphen sind jedoch eine ganz andere Angelegenheit. (Das Problem der stabilen Ehe könnte als eine Methode charakterisiert werden, wie das Problem der gewichteten Paarung für allgemeine Graphen durch Umformulierung des Problems umgangen werden kann.) Die Abhandlung der vielen Methoden, die für die Paarung bei allgemeinen Graphen ausprobiert wurden, würde ein ganzes Buch füllen; es handelt sich um eins der am intensivsten untersuchten Probleme in der Graphentheorie.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]