Re: [boost] space complexity of push_relabel_max_flow

Subject: Re: [boost] space complexity of push_relabel_max_flow
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-04-15 11:51:01

> 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