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 ‘Readme.md’ 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

Advertisements
Standard

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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