Minimum cycle bases for network graphs

The minimum cycle basis problem in a graph G = (V, E) is the task to construct a minimum length basis of its cycle vector space. A well-known algorithm by Horton of 1987 needs running time O(\Vparallel toE\(2.376)). We present a new combinatorial approach which generates minimum cycle bases in time O(max{\E\(3), \Eparallel toV\(2) log\V\}) with a space requirement of Theta(\E\(2)). This method is especially suitable for large sparse graphs of electric engineering applications since there, typically, \E\ is close to linear in \V\.