Mathematical models and a constructive heuristic for finding minimum fundamental cycle bases
DOI:
https://doi.org/10.2298/YJOR0501015LKeywords:
fundamental cycle, cycle basis, IP formulation, tree-growing heuristicAbstract
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
Brambilla, A., Premoli, A. (2001) Rigorous event-driven (red) analysis of large-scale nonlinear re circuits. IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, 48, 8, 938-946
Deo, N., Kumar, N., Parsons, J. (1995) Minimum-length fundamental-cycle set problem: New heuristics and an empirical investigation. Congressus Numerantium, 107, 141-15
Deo, N., Prabhu, G.M., Krishnamoorthy, M.S. (1982) Algorithms for generating fundamental cycles in a graph. ACM Transactions on Mathematical Software, 8, 1, 26-42
Galbiati, G., Amaldi, E. (2003) On the approximability of the minimum fundamental cycle basis problem. u: Workshop on Approximation and Online Algorithms (WAOA03), September, Budapest
Horton, J.D. (1987) A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM Journal on Computing, 16, 2, 358-366
Hubicka, E., Syslo, M. (1975) Minimal bases of cycles of a graph. u: Recent Advances in Graph Theory, 2nd Czech Symposium in Graph Theory, Academia, 283-293
Kirchhoff, G. (1847) Über die Auflösung der Gleichungen, aufweiche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Ann Phys Chem ('Poggendorfs Ammlen'), 72, 497-508
Liebchen, C., Mohring, R.H. (2002) A case study in periodic timetabling. u: Wagner D. [ur.] Electronic Notes in Theoretical Computer Science, Elsevier, Volume 66
Paton, K. (1969) An algorithm for finding a fundamental set of cycles of a graph. Communications of the ACM, 12, 9, 514-518
Seshu, S., Reed, M.B. (1961) Linear graphs and electrical networks. Reading, MA: Addison-Wesley
Syslo, M. (1978) An efficient cycle vector space algorithm for listing all cycles of a planar graph. u: Colloquia Mathematica Societatis János Bolyai, 749-762
Syslo, M. (1979) On cycle bases of a graph. Networks, 9 123-132
Syslo, M. (1981) On some problems related to fundamental cycle sets of a graph. u: Chartrand R. [ur.] Theory of Applications of Graphs, New York, itd: Wiley, 577-588
Syslo, M. (1982) On some problems related to fundamental cycle sets of a graph: Research notes. Discrete Mathematics, Warsaw, 7, 145-157
Syslo, M. (1982) On the fundamental cycle set graph. IEEE Transactions on Circuits and Systems, 29, 3, 136-138
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.