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.
- Berger, F., Gritzmann, P., and de Vries, S. 2004. Minimum cycle basis for network graphs. Algorithmica 40, 1, 51--62. Google Scholar
- Boost. 2001. C++ Libraries. http://www.boost.org.Google Scholar
- Cassell, A. C., Henderson, J. C., and Ramachandran, K. 1976. Cycle bases of minimal measure for the structural analysis of skeletal structures by the flexibility method. Proc. Royal Society of London Series A 350, 61--70.Google Scholar
- Chua, L. O. and Chen, L. 1973. On optimally sparse cycle and coboundary basis for a linear graph. IEEE Trans. Circuit Theory CT-20, 495--503.Google Scholar
- Coppersmith, D. and Winograd, S. 1990. Matrix multiplications via arithmetic progressions. Journal of Symb. Comput. 9, 251--280. Google Scholar
- de Pina, J. 1995. Applications of shortest path methods. Ph.D. thesis, University of Amsterdam, Netherlands.Google Scholar
- Golynski, A. and Horton, J. D. 2002. A polynomial time algorithm to find the minimum cycle basis of a regular matroid. In 8th Scandinavian Workshop on Algorithm Theory. Google Scholar
- Gotsman, C., Kaligosi, K., Mehlhorn, K., Michail, D., and Pyrga, E. 2005. Cycle bases of graphs and sampled manifolds. manuscript. http://www.mpi-inf.mpg.de/~michail/papers/mcb-manifold.pdf.Google Scholar
- Horton, J. D. 1987. A polynomial-time algorithm to find a shortest cycle basis of a graph. SIAM Journal of Computing 16, 359--366. Google Scholar
- Huber, M. 2002. Implementation of algorithms for sparse cycle bases of graphs. http://www-m9.ma.tum.de/dm/cycles/mhuber.Google Scholar
- Kavitha, T., Mehlhorn, K., Michail, D., and Paluch, K. E. 2004. A faster algorithm for minimum cycle basis of graphs. In 31st International Colloquium on Automata, Languages and Programming, Finland. 846--857.Google Scholar
- Kreisbasenbibliothek. 2004. CyBaL. http://www-m9.ma.tum.de/dm/cycles/cybal.Google Scholar
- Mehlhorn, K. and Michail, D. 2005. Implementing minimum cycle basis algorithms. In Experimental and Efficient Algorithms, 4th International Workshop, WEA 2005, Santorini Island, Greece, May 10--13, 2005, Proceedings, S. E. Nikoletseas, Ed. Lecture Notes in Computer Science, vol. 3503. Springer, New York. 32--43. Google Scholar
- Mehlhorn, K. and Naher, S. 1999. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge. Google Scholar
- Tewari, G., Gotsman, C., and Gortler, S. J. 2005. Meshing genus-1 point clouds using discrete one-forms. Tech. Rep. TR-14-05, Computer Science Group, Harvard University.Google Scholar
Index Terms
Implementing minimum cycle basis algorithms
Recommendations
Implementing minimum cycle basis algorithms
WEA'05: Proceedings of the 4th international conference on Experimental and Efficient AlgorithmsIn 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 + mn2log n) algorithm presented in [1]. For sparse graphs this is ...
Faster Algorithms for Minimum Cycle Basis in Directed Graphs
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph $G$ whose edges have nonnegative weights. A cycle in this graph is actually a cycle in the underlying undirected graph with ...
An $\tilde{O}(m^{2}n)$Algorithm for Minimum Cycle Basis of Graphs
We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over $\mathbb{F}_{2}$...
Comments