In this work we present an exact separation algorithm for the so called co-circuit inequalities, otherwise known as parity or 2-matching inequalities. The algorithm is quite simple since it operates on the tree of min-cuts of the support graph of the solution to separate, relative to an ad hoc capacity vector. The order of our algorithm is O(|V|^4) which is considerably smaller to that of other algorithms proposed in the literature, which is O((|V|+|E|)^4).
Citation
Technical University of Catalonia. Jordi Girona 1-3, 08034 Barcelona, Spain. November, 2007.