Minimum Cycle Basis, Algorithms & Applications

Dimitrios Michail, Markus Bläser, Kurt MehlhornMPG.PuRe 2006

Abstract

We consider the problem of computing a minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices. In this problem, a {0, 1} incidence vector is associated with each cycle and the vector space over F2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis of its cycle space. A cycle basis where the sum of the weights of its cycles is minimum is called a minimum cycle basis of G. Minimum cycle bases are useful in a number of contexts, e.g., the analysis of electrical networks, structural engineering, and chemistry. We present an O(m2n + mn2 log n) algorithm to compute a minimum cycle basis. The previously best known running time to compute a minimum cycle basis was O(mωn), where ω is the exponent of matrix multiplication. It is presently known that ω 0 we design a fast (1 + )-approximation algorithm by using approximate shortest cycles computations. Moreover, for any integer k ≥ 1 we present two constant factor approximate algorithms with approximation factor 2k − 1. One of them has an expected running time of O(kmn1+2/k +mn(1+1/k)(ω−1)) while the other has a deterministic O(n3+2/k) running time. For sufficiently dense graphs these running times are o(mω). For special cases of graphs like geometric or planar graphs we present even faster approximation algorithms. Our techniques extend to the directed minimum cycle basis problem. We also study the minimum cycle basis problem from a practical perspective. We describe how to efficiently implement de Pina’s O(m3 +mn2 log n) algorithm. We develop several heuristics which decrease the running time
BibTeX
@inproceedings{michail2006minimum,
  author = {Dimitrios Michail and Markus Bläser and Kurt Mehlhorn},
  title = {{Minimum Cycle Basis, Algorithms \& Applications}},
  booktitle = {MPG.PuRe},
  year = {2006},
}

Loading related content...

Figure