Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases

Authors

  • Leo Liberti DEI, Politecnico di Milano, Milano, Italy
  • Edoardo Amaldi DEI, Politecnico di Milano, Milano, Italy
  • Francesco Maffioli DEI, Politecnico di Milano, Milano, Italy
  • Nelson Maculan COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, Brazil

DOI:

https://doi.org/10.2298/YJOR0501015L

Keywords:

fundamental cycle, cycle basis, IP formulation, tree-growing heuristic

Abstract

The problem of finding a fundamental cycle basis with minimum total cost in a graph arises in many application fields. In this paper we present some integer linear programming formulations and we compare their performances, in terms of instance size, CPU time required for the solution, and quality of the associated lower bound derived by solving the corresponding continuous relaxations. Since only very small instances can be solved to optimality with these formulations and very large instances occur in a number of applications, we present a new constructive heuristic and compare it with alternative heuristics.

References

Amaldi, E., and Rizzi, R., Personal communication, 2003.

Brambilla, A., and Premoli, A., "Rigorous event-driven (red) analysis of large-scale nonlinear rc circuits", IEEE Transactions on Circuits and Systems–I: Fundamental Theory and Applications, 48 (8) (2001) 938–946.

Deo, N., Kumar, N., and Parsons, J., "Minimum-length fundamental-cycle set problem: New heuristics and an empirical investigation", Congressus Numerantium, 107 (1995) 141–154.

Deo, N., Prabhu, G.M., and Krishnamoorthy, M.S., "Algorithms for generating fundamental cycles in a graph", ACM Transactions on Mathematical Software, 8(1) (1982) 26–42.

Galbiati, G., and Amaldi, E., "On the approximability of the minimum fundamental cycle basis problem", Workshop on Approximation and Online Algorithms (WAOA03), Budapest, September 2003.

Horton, J.D., "A polynomial-time algorithm to find the shortest cycle basis of a graph", SIAM Journal of Computing, 16(2) (1987) 358–366.

Hubicka, E., and Sysło, M., "Minimal bases of cycles of a graph", in: Recent Advances in Graph Theory, 2nd Czech Symposium in Graph Theory, Academia, 1975, 283–293.

Kirchhoff, G., "Über die auflösung der gleichungen, auf welche man bei der untersuchungen der linearen verteilung galvanisher ströme geführt wird", Poggendorf Annalen Physik, 72 (1847) 497–508.

Liebchen, C., and Möhring, R.H., "A case study in periodic timetabling", in: D. Wagner (ed), Electronic Notes in Theoretical Computer Science, Volume 66. Elsevier, 2002.

Paton, K., "An algorithm for finding a fundamental set of cycles of a graph", Communications of the ACM, 12(9) (1969) 514–518.

Seshu, S., and Reed, M.B., Linear Graphs and Electrical Networks. Addison-Wesley, Reading, MA, 1961.

Sysło, M., "An efficient cycle vector space algorithm for listing all cycles of a planar graph", Colloquia Mathematica Societatis János Bolyai, 1978, 749–762.

Sysło, M., "On cycle bases of a graph", Networks, 9 (1979) 123–132.

Sysło, M., "On some problems related to fundamental cycle sets of a graph", in: R. Chartrand (ed.), Theory of Applications of Graphs, Wiley, New York, 1981, 577–588.

Sysło, M., "On some problems related to fundamental cycle sets of a graph: Research notes", Discrete Mathematics (Banach Centre Publications, Warsaw), 7 (1982) 145–157.

Sysło, M., "On the fundamental cycle set graph", IEEE Transactions on Circuits and Systems, 29(3) (1982) 136–138.

Downloads

Published

2005-03-01

Issue

Vol. 15 No. 1 (2005)

Section

Research Articles

License

Copyright (c) 2005 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.