Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Implementing Minimum Cycle Basis Algorithms


Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Michail,  Dimitrios
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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

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
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.