[boost] Complexity of Goldberg's push_relabel max flow algorithm used in BOOST

Subject: [boost] Complexity of Goldberg's push_relabel max flow algorithm used in BOOST
From: Dan Jiang (danjiang_at_[hidden])
Date: 2010-07-05 21:03:07

Anyone knows the time complexity of the Goldberg's push_relabel max flow algorithm used in BOOST? The BOOST documentation says O(n^3). But since the code seems to use highest label, global and gap relabeling and hence the complexity should be O(n^2 * m^1/2).  According to literature, the complexity would be O(n^3) if FIFO is used in implementation.
Please correct if I am wrong.
Dan 		 	   		  
_________________________________________________________________
Look 'em in the eye: FREE Messenger video chat
http://go.microsoft.com/?linkid=9734386