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.
Look 'em in the eye: FREE Messenger video chat
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk