An $\tilde{O}(m^{2}n)$ Algorithm for Minimum Cycle Basis of Graphs

• DOI: 10.1007/s00453-007-9064-z
• Publication Date: 2007-10-12T17:56:40Z
• Authors: Telikepalli Kavitha; Kurt Mehlhorn; Dimitrios Michail; Katarzyna E. Paluch
• Keywords: Cycle basis; Basis (linear algebra)

We consider the problem of computing a minimum cycle basis an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, {0,1} incidence vector is associated each space over $\mathbb{F}_{2}$ generated by these vectors G. A set cycles called if it forms for its space. where sum weights Minimum are useful in number contexts, e.g. analysis electrical networks structural engineering. The previous best algorithm has running time O(m ω n), exponent matrix multiplication. It presently known that ω<2.376. exhibit 2 n+mn 2log n) algorithm. When edge integers, we have For unweighted graphs which reasonably dense, our runs ) time. any ε>0, also design 1+ε approximation O((m /ε)log (W/ε)) dense graphs, W largest weight.