{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:33:07Z","timestamp":1760707987808},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,10,21]],"date-time":"2008-10-21T00:00:00Z","timestamp":1224547200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2009,5]]},"DOI":"10.1007\/s00186-008-0255-4","type":"journal-article","created":{"date-parts":[[2008,10,20]],"date-time":"2008-10-20T13:08:17Z","timestamp":1224508097000},"page":"205-233","source":"Crossref","is-referenced-by-count":10,"title":["Edge-swapping algorithms for the minimum fundamental cycle basis problem"],"prefix":"10.1007","volume":"69","author":[{"given":"Edoardo","family":"Amaldi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leo","family":"Liberti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Maffioli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nelson","family":"Maculan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,10,21]]},"reference":[{"key":"255_CR1","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N Alon","year":"1995","unstructured":"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\u2013100","journal-title":"SIAM J Comput"},{"key":"255_CR2","first-page":"15","volume-title":"Experimental and efficient algorithms\u2014WEA2004 proceedings, Lecture Notes in Computer Science, vol 3059","author":"E Amaldi","year":"2004","unstructured":"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\u2014WEA2004 proceedings, Lecture Notes in Computer Science, vol 3059. Springer, Heidelberg, pp 15\u201329"},{"issue":"8","key":"255_CR3","doi-asserted-by":"crossref","first-page":"938","DOI":"10.1109\/81.940184","volume":"48","author":"A Brambilla","year":"2001","unstructured":"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\u2013946","journal-title":"IEEE Trans Circuits Syst I Fundam Theory Appl"},{"issue":"1","key":"255_CR4","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/355984.355988","volume":"8","author":"N Deo","year":"1982","unstructured":"Deo N, Prabhu G, Krishnamoorthy M (1982) Algorithms for generating fundamental cycles in a graph. ACM Trans Math Softw 8(1): 26\u201342","journal-title":"ACM Trans Math Softw"},{"key":"255_CR5","first-page":"141","volume":"107","author":"N Deo","year":"1995","unstructured":"Deo N, Kumar N, Parsons J (1995) Minimum-length fundamental-cycle set problem: new heuristics and an empirical investigation. Congressus Numerantium 107: 141\u2013154","journal-title":"Congressus Numerantium"},{"key":"255_CR6","doi-asserted-by":"crossref","unstructured":"Elkin M, Emek Y, Spielman D, Teng S-H (2005) Lower-stretch spanning trees. In: STOC \u201905: Proceedings of the 37th annual ACM symposium on theory of computing, ACM, New York, pp 494\u2013503","DOI":"10.1145\/1060590.1060665"},{"key":"255_CR7","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/j.ipl.2007.06.013","volume":"104","author":"M Elkin","year":"2007","unstructured":"Elkin M, Liebchen C, Rizzi R (2007) New length bounds for cycle bases. Inf Process Lett 104: 186\u2013193","journal-title":"Inf Process Lett"},{"issue":"3","key":"255_CR8","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/net.10022","volume":"93","author":"M Fischetti","year":"2002","unstructured":"Fischetti M, Lancia G, Serafini P (2002) Exact algorithms for minimum routing cost trees. Networks 93(3): 161\u2013173","journal-title":"Networks"},{"issue":"3","key":"255_CR9","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1137\/0207024","volume":"7","author":"H Gabow","year":"1978","unstructured":"Gabow H, Myers E (1978) Finding all spanning trees of directed and undirected graphs. SIAM J Comput 7(3): 280\u2013287","journal-title":"SIAM J Comput"},{"key":"255_CR10","unstructured":"Galbiati G, Rizzi R, Amaldi E (2007) On the approximability of the minimum strictly fundamental cycle bases problem. Technical Report, DEI, Politecnico di Milano"},{"key":"255_CR11","unstructured":"Guta B (2003) Subgradient optimization methods in integer programming, with an application to a radiation therapy problem. PhD thesis, Kaiserslautern University"},{"key":"255_CR12","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1016\/S0377-2217(00)00100-4","volume":"130","author":"P Hansen","year":"2001","unstructured":"Hansen P, Mladenovi\u0107 N (2001) Variable neighbourhood search: principles and applications. Eur J Oper Res 130: 449\u2013467","journal-title":"Eur J Oper Res"},{"key":"255_CR13","volume-title":"Handbook of applied optimization","author":"P Hansen","year":"2002","unstructured":"Hansen P, Mladenovi\u0107 N (2002) Variable neighbourhood search. In: Pardalos P, Resende M (eds) Handbook of applied optimization. Oxford University Press, Oxford"},{"issue":"1","key":"255_CR14","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1002\/jgt.3190130115","volume":"13","author":"D Hartvigsen","year":"1989","unstructured":"Hartvigsen D, Zemel E (1989) Is every cycle basis fundamental? J Graph Theory 13(1): 117\u2013137","journal-title":"J Graph Theory"},{"key":"255_CR15","first-page":"121","volume-title":"Local search in combinatorial optimization","author":"A Hertz","year":"1997","unstructured":"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\u2013136"},{"issue":"2","key":"255_CR16","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1137\/0216026","volume":"16","author":"J Horton","year":"1987","unstructured":"Horton J (1987) A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J Comput 16(2): 358\u2013366","journal-title":"SIAM J Comput"},{"key":"255_CR17","unstructured":"Hubicka E, Sys\u0142o 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\u2013293"},{"key":"255_CR18","unstructured":"ILOG (2002) ILOG CPLEX 8.0 User\u2019s Manual, ILOG S.A., Gentilly, France"},{"key":"255_CR19","unstructured":"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\u2013857"},{"key":"255_CR20","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1002\/andp.18471481202","volume":"72","author":"G Kirchhoff","year":"1847","unstructured":"Kirchhoff G (1847) \u00dcber die aufl\u00f6sung der gleichungen, auf welche man bei der untersuchungen der linearen verteilung galvanischer str\u00f6me gef\u00fchrt wird. Poggendorf Ann Phys 72: 497\u2013508","journal-title":"Poggendorf Ann Phys"},{"key":"255_CR21","doi-asserted-by":"crossref","unstructured":"Liebchen C (2003) Finding short integral cycle bases for cyclic timetabling. In: Algorithms\u2014ESA2003 proceedings, Lecture Notes in Computer Science, vol 2832. Springer, Heidelberg, pp 715\u2013726","DOI":"10.1007\/978-3-540-39658-1_64"},{"key":"255_CR22","volume-title":"Electronic notes in theoretical computer science, vol 66","author":"C Liebchen","year":"2002","unstructured":"Liebchen C, M\u00f6hring R (2002) A case study in periodic timetabling. In: Wagner D (eds) Electronic notes in theoretical computer science, vol 66. Elsevier, Amsterdam"},{"key":"255_CR23","first-page":"365","volume-title":"Experimental algorithms\u2014WEA 2007, Lecture Notes in Computer Science, vol 4525","author":"C Liebchen","year":"2007","unstructured":"Liebchen C, W\u00fcnsch G, K\u00f6hler E, Reich A, Rizzi R (2007) Benchmarks for strictly fundamental cycle bases. In: Demetrescu C (eds) Experimental algorithms\u2014WEA 2007, Lecture Notes in Computer Science, vol 4525. Springer, New York, pp 365\u2013378"},{"issue":"1","key":"255_CR24","doi-asserted-by":"crossref","first-page":"15","DOI":"10.2298\/YJOR0501015L","volume":"15","author":"L Liberti","year":"2005","unstructured":"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\u201324","journal-title":"Yugoslav J Oper Res"},{"key":"255_CR25","unstructured":"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"},{"issue":"1","key":"255_CR26","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1145\/204865.204889","volume":"38","author":"K Mehlhorn","year":"1995","unstructured":"Mehlhorn K, N\u00e4her S (1995) LEDA: a platform for combinatorial and geometric computing. Commun ACM 38(1): 96\u2013102","journal-title":"Commun ACM"},{"issue":"9","key":"255_CR27","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1145\/363219.363232","volume":"12","author":"K Paton","year":"1969","unstructured":"Paton K (1969) An algorithm for finding a fundamental set of cycles of a graph. Commun ACM 12(9): 514\u2013518","journal-title":"Commun ACM"},{"issue":"3","key":"255_CR28","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1137\/S0097539794270881","volume":"26","author":"A Shioura","year":"1997","unstructured":"Shioura A, Tamura A, Uno T (1997) An optimal algorithm for scanning all spanning trees of undirected graphs. SIAM J Comput 26(3): 678\u2013692","journal-title":"SIAM J Comput"},{"issue":"4","key":"255_CR29","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1137\/0402049","volume":"2","author":"P Serafini","year":"1989","unstructured":"Serafini P, Ukovich W (1989) A mathematical model for periodic scheduling problems. SIAM J Discrete Math 2(4): 550\u2013581","journal-title":"SIAM J Discrete Math"},{"key":"255_CR30","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1021\/c160016a007","volume":"5","author":"EJ Sussenouth","year":"1965","unstructured":"Sussenouth EJ (1965) A graph theoretical algorithm for matching chemical structures. J Chem Doc 5: 36\u201343","journal-title":"J Chem Doc"},{"key":"255_CR31","unstructured":"Sys\u0142o M (1978) An efficient cycle vector space algorithm for listing all cycles of a planar graph, Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp 749\u2013762"},{"key":"255_CR32","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1002\/net.3230090203","volume":"9","author":"M Sys\u0142o","year":"1979","unstructured":"Sys\u0142o M (1979) On cycle bases of a graph. Networks 9: 123\u2013132","journal-title":"Networks"},{"key":"255_CR33","first-page":"577","volume-title":"Theory of applications of graphs","author":"M Sys\u0142o","year":"1981","unstructured":"Sys\u0142o 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\u2013588"},{"key":"255_CR34","first-page":"145","volume":"7","author":"M Sys\u0142o","year":"1982","unstructured":"Sys\u0142o M (1982) On some problems related to fundamental cycle sets of a graph: research notes. Discrete Math 7: 145\u2013157","journal-title":"Discrete Math"},{"issue":"3","key":"255_CR35","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1109\/TCS.1982.1085125","volume":"29","author":"M Sys\u0142o","year":"1982","unstructured":"Sys\u0142o M (1982) On the fundamental cycle set graph. IEEE Trans Circuits Syst 29(3): 136\u2013138","journal-title":"IEEE Trans Circuits Syst"},{"key":"255_CR36","unstructured":"Vismara P (1995) Reconnaissance et repr\u00e9sentation d\u2019\u00e9l\u00e9ments structuraux pour la description d\u2019objets complexes. application \u00e0 l\u2019\u00e9laboration de strat\u00e9gies de synth\u00e8se en chimie organique, PhD thesis, Universit\u00e9 de Montpellier II, France"},{"key":"255_CR37","first-page":"761","volume":"29","author":"BY Wu","year":"1999","unstructured":"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\u2013778","journal-title":"SIAM J Comput"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-008-0255-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00186-008-0255-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-008-0255-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T14:33:28Z","timestamp":1558622008000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00186-008-0255-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,21]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["255"],"URL":"https:\/\/doi.org\/10.1007\/s00186-008-0255-4","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"value":"1432-2994","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,21]]}}}