nicht angemeldet
Hi
Intuitiv würde ich sagen der einzige Weg wäre eine Verkürzung auf einen ungerichetetn Graphen, d.h. du ermittelst nur die zulässigen Kanten zwischen A und B die man ungestraft wählen dürfte (A mag B am meisten und B mag A am meisten), das ist linear zu der Zahl der Einträge in der matrix.
Schritt 1:
für alle a in A und b in B: alle Kanten (a,b) streichen für die (a,b') existiert mit w(a,b') < w(a,b). Analog für (b,a).
Schritt 2:
Nur die unegrichteten Kanten (a,b ) stehen lassen für die sowohl (a,b) als auch (b,a) existieren.
Tschau
LanX