The first part concentrates on new structural results which might help to decide if the minimum weight cycle basis problem (MCB) for integral and totally unimodular bases is in P or is NP-complete. A new potentially useful class of double cover bases is also presented. The main reason for research in this area is the fact that known algorithms for finding MCBs in general graphs return bases with rather poor theoretical properties.
In the second part we present an algorithm for computing general minimum weight cycle bases in time O(Eω) for general graphs; here V and E denote the number of nodes and edges, respectively, and ω is the exponent of the fastest matrix multiplication algorithm. Our algorithm is the first to run faster than Õ(E2V). A key ingredient to our improved running time is the insight that the search for the minimum basis can be restricted to a set of candidate cycles of total length O(V E).