hide
Free keywords:
-
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(m3 + mn2 log n) algorithm. For sparse
graphs, this is the currently best-known algorithm. This algorithm's running
time can be partitioned into two parts with time O(m3) and O(m2n + mn2 log
n), respectively. Our experimental findings imply that for random graphs the
true bottleneck of a sophisticated implementation is the O(m2 n + mn2 log
n) part. A straightforward implementation would require Ω(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 speed-up. Based on our experimental observations, we combine the
two fundamentally different approaches to compute a minimum cycle basis to
obtain a new hybrid algorithm with running time O(m2n2). 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 of an undirected graph.
