A faster algorithm for Minimum Cycle Basis of graphs

The vector space over GF(2) generated by the incidence vectors of
cycles is called the cycle space of a graph. A minimum cycle basis is
a basis of the cycle space which has minimum weight among all the
bases of the cycle space (we assume that the edges of the graph
have non-negative weights). We give an O(m^2n + mn^2logn) algorithm
to compute a minimum cycle basis, where m is the number of edges
in the graph and n is the number of vertices. The previous best
algorithm for this problem had a running time of O(m^{omega}n),
where omega is the best exponent of matrix multiplication.
Our algorithm also uses fast matrix multiplication.

Joint work with Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch.