Abstract
We consider the problem of finding a fundamental cycle basis with minimum total cost in an undirected graph. This problem is NP-hard and has several interesting applications. Since fundamental cycle bases correspond to spanning trees, we propose a local search algorithm, a tabu search and variable neighborhood search in which edge swaps are iteratively applied to a current spanning tree. We also present a mixed integer programming formulation of the problem whose linear relaxation yields tighter lower bounds than other known formulations. Computational results obtained with our algorithms are compared with those from the best available constructive heuristic on several types of graphs.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alon N, Karp R, Peleg D, West D (1995) A graph-theoretic game and its application to the k-server problem. SIAM J Comput 24: 78–100
Amaldi E, Liberti L, Maculan N, Maffioli F (2004) Efficient edge-swapping heuristics for finding minimum fundamental cycle bases. In: Ribeiro C, Martins S (eds) Experimental and efficient algorithms—WEA2004 proceedings, Lecture Notes in Computer Science, vol 3059. Springer, Heidelberg, pp 15–29
Brambilla A, Premoli A (2001) Rigorous event-driven (red) analysis of large-scale nonlinear rc circuits. IEEE Trans Circuits Syst I Fundam Theory Appl 48(8): 938–946
Deo N, Prabhu G, Krishnamoorthy M (1982) Algorithms for generating fundamental cycles in a graph. ACM Trans Math Softw 8(1): 26–42
Deo N, Kumar N, Parsons J (1995) Minimum-length fundamental-cycle set problem: new heuristics and an empirical investigation. Congressus Numerantium 107: 141–154
Elkin M, Emek Y, Spielman D, Teng S-H (2005) Lower-stretch spanning trees. In: STOC ’05: Proceedings of the 37th annual ACM symposium on theory of computing, ACM, New York, pp 494–503
Elkin M, Liebchen C, Rizzi R (2007) New length bounds for cycle bases. Inf Process Lett 104: 186–193
Fischetti M, Lancia G, Serafini P (2002) Exact algorithms for minimum routing cost trees. Networks 93(3): 161–173
Gabow H, Myers E (1978) Finding all spanning trees of directed and undirected graphs. SIAM J Comput 7(3): 280–287
Galbiati G, Rizzi R, Amaldi E (2007) On the approximability of the minimum strictly fundamental cycle bases problem. Technical Report, DEI, Politecnico di Milano
Guta B (2003) Subgradient optimization methods in integer programming, with an application to a radiation therapy problem. PhD thesis, Kaiserslautern University
Hansen P, Mladenović N (2001) Variable neighbourhood search: principles and applications. Eur J Oper Res 130: 449–467
Hansen P, Mladenović N (2002) Variable neighbourhood search. In: Pardalos P, Resende M (eds) Handbook of applied optimization. Oxford University Press, Oxford
Hartvigsen D, Zemel E (1989) Is every cycle basis fundamental? J Graph Theory 13(1): 117–137
Hertz A, Taillard E, de Werra D (1997) Tabu search. In: Aarts E, Lenstra J (eds) Local search in combinatorial optimization. Wiley, Chichester, pp 121–136
Horton J (1987) A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J Comput 16(2): 358–366
Hubicka E, Sysło M (1975) Minimal bases of cycles of a graph. In: Recent advances in graph theory, second Czech symposium in graph theory. Academia, Prague, pp 283–293
ILOG (2002) ILOG CPLEX 8.0 User’s Manual, ILOG S.A., Gentilly, France
Kavitha T, Mehlhorn K, Michail D, Paluch K (2004) A faster algorithm for minimum cycle bases of graphs. In: Proceedings of ICALP, Lecture Notes in Computer Science, vol 3124. Springer, Heidelberg, pp 846–857
Kirchhoff G (1847) Über die auflösung der gleichungen, auf welche man bei der untersuchungen der linearen verteilung galvanischer ströme geführt wird. Poggendorf Ann Phys 72: 497–508
Liebchen C (2003) Finding short integral cycle bases for cyclic timetabling. In: Algorithms—ESA2003 proceedings, Lecture Notes in Computer Science, vol 2832. Springer, Heidelberg, pp 715–726
Liebchen C, Möhring R (2002) A case study in periodic timetabling. In: Wagner D (eds) Electronic notes in theoretical computer science, vol 66. Elsevier, Amsterdam
Liebchen C, Wünsch G, Köhler E, Reich A, Rizzi R (2007) Benchmarks for strictly fundamental cycle bases. In: Demetrescu C (eds) Experimental algorithms—WEA 2007, Lecture Notes in Computer Science, vol 4525. Springer, New York, pp 365–378
Liberti L, Amaldi E, Maculan N, Maffioli F (2005) Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases. Yugoslav J Oper Res 15(1): 15–24
Lissoni L (2003) Implementazione di un algoritmo efficiente per determinare una base di cicli minima di un grafo, tesi di Laurea, DEI, Politecnico di Milano
Mehlhorn K, Näher S (1995) LEDA: a platform for combinatorial and geometric computing. Commun ACM 38(1): 96–102
Paton K (1969) An algorithm for finding a fundamental set of cycles of a graph. Commun ACM 12(9): 514–518
Shioura A, Tamura A, Uno T (1997) An optimal algorithm for scanning all spanning trees of undirected graphs. SIAM J Comput 26(3): 678–692
Serafini P, Ukovich W (1989) A mathematical model for periodic scheduling problems. SIAM J Discrete Math 2(4): 550–581
Sussenouth EJ (1965) A graph theoretical algorithm for matching chemical structures. J Chem Doc 5: 36–43
Sysło M (1978) An efficient cycle vector space algorithm for listing all cycles of a planar graph, Colloquia Mathematica Societatis János Bolyai, pp 749–762
Sysło M (1979) On cycle bases of a graph. Networks 9: 123–132
Sysło M (1981) On some problems related to fundamental cycle sets of a graph. In: Chartrand R (eds) Theory of applications of graphs. Wiley, New York, pp 577–588
Sysło M (1982) On some problems related to fundamental cycle sets of a graph: research notes. Discrete Math 7: 145–157
Sysło M (1982) On the fundamental cycle set graph. IEEE Trans Circuits Syst 29(3): 136–138
Vismara P (1995) Reconnaissance et représentation d’éléments structuraux pour la description d’objets complexes. application à l’élaboration de stratégies de synthèse en chimie organique, PhD thesis, Université de Montpellier II, France
Wu BY, Lancia G, Bafna V, Chao R, Ravi K-M, Tang C (1999) A polynomial-time approximation scheme for minimum routing cost spanning trees. SIAM J Comput 29: 761–778
Author information
Authors and Affiliations
Corresponding author
Additional information
This article extends the conference paper (Amaldi et al. 2004).
Rights and permissions
About this article
Cite this article
Amaldi, E., Liberti, L., Maffioli, F. et al. Edge-swapping algorithms for the minimum fundamental cycle basis problem. Math Meth Oper Res 69, 205–233 (2009). https://doi.org/10.1007/s00186-008-0255-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-008-0255-4