Calculating max-flow using push-relabel method

Dilawar's Notes

Calculating maximum flow in a flow-network is a fundamental problem. It has been observed that smart implementation of ‘push-relabel’ methods performs better than algorithms based on finding ‘augmenting paths’. We have implemented one such variation of push-relabel method. It is known as ‘relabel to front’ algorithm. It is discussed in details in ‘Introduction to algorithms’ by ‘Cormen, Leiserson, Rivest, and Stein’.

We do not guarantee that it is the exact implementation of what is given in this book. In fact, it is slightly different for we are selecting nodes in some fixed order. We uses boost::graph library. Details are in ‘’ file. It is available on my github repository. You can use it, but you are not allowed to modify it without notifying the author. I wish to keep track of bugs.

View original post


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s