Campus Event Calendar

Event Entry

What and Who

Implementing minimum cycle basis algorithms

Dimitris Michail
Max-Planck-Institut für Informatik - AG 1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Monday, 18 April 2005
30 Minutes
46.1 - MPII


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.

Joint work with Kurt Mehlhorn.


Dimitrios Michail
--email hidden
passcode not visible
logged in users only

Dimitrios Michail, 03/23/2005 15:23
Dimitrios Michail, 03/23/2005 12:04 -- Created document.