skip to main content
article

Implementing minimum cycle basis algorithms

Published:09 February 2007Publication History
Skip Abstract Section

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.

References

  1. Berger, F., Gritzmann, P., and de Vries, S. 2004. Minimum cycle basis for network graphs. Algorithmica 40, 1, 51--62. Google ScholarGoogle Scholar
  2. Boost. 2001. C++ Libraries. http://www.boost.org.Google ScholarGoogle Scholar
  3. 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 ScholarGoogle Scholar
  4. 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 ScholarGoogle Scholar
  5. Coppersmith, D. and Winograd, S. 1990. Matrix multiplications via arithmetic progressions. Journal of Symb. Comput. 9, 251--280. Google ScholarGoogle Scholar
  6. de Pina, J. 1995. Applications of shortest path methods. Ph.D. thesis, University of Amsterdam, Netherlands.Google ScholarGoogle Scholar
  7. 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 ScholarGoogle Scholar
  8. 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 ScholarGoogle Scholar
  9. 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 ScholarGoogle Scholar
  10. Huber, M. 2002. Implementation of algorithms for sparse cycle bases of graphs. http://www-m9.ma.tum.de/dm/cycles/mhuber.Google ScholarGoogle Scholar
  11. 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 ScholarGoogle Scholar
  12. Kreisbasenbibliothek. 2004. CyBaL. http://www-m9.ma.tum.de/dm/cycles/cybal.Google ScholarGoogle Scholar
  13. 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 ScholarGoogle Scholar
  14. Mehlhorn, K. and Naher, S. 1999. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge. Google ScholarGoogle Scholar
  15. 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 ScholarGoogle Scholar

Index Terms

  1. Implementing minimum cycle basis algorithms

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in

    Full Access

    • Published in

      cover image ACM Journal of Experimental Algorithmics
      ACM Journal of Experimental Algorithmics  Volume 11, Issue
      2006
      355 pages
      ISSN:1084-6654
      EISSN:1084-6654
      DOI:10.1145/1187436
      Issue’s Table of Contents

      Copyright © 2007 ACM

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 9 February 2007
      Published in jea Volume 11, Issue

      Qualifiers

      • article

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader