# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Implementing Minimum Cycle Basis Algorithms

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Mehlhorn, K., & Michail, D. (2005). Implementing Minimum Cycle Basis Algorithms.
In *Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005* (pp. 32-43).
Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-26BF-0

##### Abstract

In this paper we consider the problem of computing a minimum cycle basis of an
undirected graph $G = (V,E)$ with $n$ vertices and $m$ edges. We describe an
efficient implementation of an $O(m^3 + mn^2\log n)$ algorithm presented
in~\cite{PINA95}. For sparse graphs this is the currently best known algorithm.
This algorithm's running time can be partitioned into two parts
with time $O(m^3)$ and $O( m^2n + mn^2 \log n)$ respectively.
Our experimental findings imply that the true bottleneck of a
sophisticated implementation is the $O( m^2 n + mn^2 \log n)$ part. A
straightforward implementation would require $\Omega(nm)$ shortest path
computations, thus we develop several heuristics in order to get a practical
algorithm. Our experiments show that in random graphs our techniques result in
a significant speedup.
Based on our experimental observations, we combine the two fundamentally
different approaches to compute a minimum cycle basis used
in~\cite{PINA95,KMMP04} and~\cite{HOR87,MATR02}, to obtain a new hybrid
algorithm with running time
$O( m^2 n^2 )$. The hybrid algorithm is very efficient in practice for random
dense unweighted graphs.
Finally, we compare these two algorithms with a number of previous
implementations for finding a minimum cycle basis in an undirected graph.