patternMinor
Ford-Fulkerson algorithm with asymmetric adjacency matrix
Viewed 0 times
asymmetricwithalgorithmfulkersonfordadjacencymatrix
Problem
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?
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?
Solution
The algorithm doesn't need a symmetric adjacency matrix. It needs to keep track of a flow and a residual network. Both are supported on the edges of $G$ and their inverses. You can store them in roughly the same way you store your graph $G$, using the same amount of space (up to a multiplicative constant).
Context
StackExchange Computer Science Q#57321, answer score: 3
Revisions (0)
No revisions yet.