Cycles in graphs play an important role in many applications, e.g. analysis of electrical networks, analysis of chemical and biological pathways, periodic scheduling, and graph drawing. Cycle bases are a compact description of the set of all cycles of a graph and cycle bases consisting of short cycles or, in weighted graphs, of small weight cycles are preferable.
We present an algorithm for computing general minimum weight cycle bases in time O(E^omega) for general graphs; here V and E denote the number of nodes and edges, respectively, and omega is the exponent ofthe fastest matrix multiplication algorithm. Our algorithm is the first to run faster than Õ(E^2 V). A key 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).