Re: [boost] space complexity of push_relabel_max_flow

I've looked at push-relabel max-flow a lot and I can say the implementation is not particularly space efficient. One of the issues is that you have to store both forward and backward edges in the graph. That is how the algorithm was designed, but I think one could modify it to only use a single edge with forward and backward capacity maps.

Actually, you probably don't even need two maps -- the flow is skew-symmetric, so the flow itself doesn't need to be stored in both directions. The capacities might differ, though (although one of them is zero in Dan's code), and the residuals may need to be stored for both directions. -- Jeremiah Willcock