質問

Suppose that I have a bipartite graph $G=(A \cup B, E)$ and $A = \{1, 2, \dots, n\}$, $B = \{1, 2, \dots, m\}$. After a virtual sink $s = 0$ and a source $t = n+1$ is included into the graph, I want to implement Ford-Fulkersen max flow algorithm.

To the algorithm, we need a symmetric adjacency matrix, therefore $O((n + m)^2)$ space.

However, in a bipartite graph, it is enough to use an adjacency matrix with $O(nm)$ space. But I could not figure out how to modify the algorithm so that it works with an asymmetric adjacency matrix.

Is there any way that Ford-Fulkersen max flow algorithm works in above scenario?

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top