Kruze Frage: Wir sollen an der Uni den Push-Relabel-Algorithmus von Tarjan implementieren. Um die Kanten eines Knotens im Residualgraphen zu ermitteln, füge ich momentan nicht wirklich eine neue Kante in den Graphen ein, sondern betrachte alle ausgehenden und eingehenden Kanten im ursprünglichen Graphen und ermittle die freie Kapazität (u(e) - f(e) für ausgehende Kanten). Dabei muss man nur beachten, dass bei eingehenden Kanten, die Kapazität einfach nur der aktuelle Flusswert über die Kante ist ( Wert der rückläufigen Kante im Residualgraph hat genau diese Kapazität ). Kanten die voll ausgelastet sind, werden im Graphen nicht gelöscht, beim durchlaufen stelle ich einfach nur fest, ob die "freie Kapazität" größer null ist. Frage jetzt: Währe es schneller wenn ich den Graphen wirklich jedes mal manipulieren würde bzw. ändert das etwas an der Laufzeit von O(n²m)?