Alle Paare maximaler Fluss

8

In einem gerichteten gewichteten Diagramm finden Sie den Maximalen Fluss (oder Minimaler Kantenschnitt ) zwischen allen Knotenpaaren.
Der naive Ansatz besteht einfach darin Rufen Sie einen Max Flow Algorithmus wie Dinic's auf, dessen Komplexität O((V^2)*E) ist, für jedes Paar.
Daher ist es für alle Paare O((V^4)*E) .

Ist es möglich, die Komplexität auf O((V^3)*E) oder O(V^3) durch einige Optimierungen zu reduzieren?

    
sabari 21.12.2012, 12:59
quelle

2 Antworten

3

Gomory-Hu Tree funktioniert nicht mit gerichteten Graphen , abgesehen davon, dass Gomory-Hu Tree einen Graphen-Maximum-Flow bildet, indem er minimale Schnitte anwendet.

Die Zeitkomplexität ist:

%Vor%

* mit einem optimalen Algorithmus minimum-cut ( Max-Flow Min-Cut Reduzierung )

Dieses Beispiel zeigt, wie Gomory-Hu Tree aus einem gegebenen Graph     

Khaled.K 07.04.2013 08:00
quelle
2

Gomory-Hu-Baum funktioniert nicht für gerichtete gewichtete Graphen.

Es ist ein offenes Problem, ob es einen Algorithmus gibt, der den maximalen Fluss aller Paare schneller löst als n 2 maximale Flüsse auf gerichteten Graphen.

    
Chao Xu 21.06.2014 01:13
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Komponententests - Festlegen von privaten Mitgliedern, um den gewünschten Objektstatus zu erhalten