{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T07:09:01Z","timestamp":1774940941003,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642020933","type":"print"},{"value":"9783642020940","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02094-0_2","type":"book-chapter","created":{"date-parts":[[2009,6,27]],"date-time":"2009-06-27T14:45:07Z","timestamp":1246113907000},"page":"34-49","source":"Crossref","is-referenced-by-count":2,"title":["Minimum Cycle Bases and Their Applications"],"prefix":"10.1007","author":[{"given":"Franziska","family":"Berger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Gritzmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven","family":"de Vries","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","volume-title":"Algebraic Graph Theory","author":"N. Biggs","year":"1993","unstructured":"Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1993)"},{"key":"2_CR2","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R. Diestel","year":"1997","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol.\u00a0173. Springer, Heidelberg (1997)"},{"key":"2_CR3","volume-title":"Matroid Theory","author":"J.G. Oxley","year":"1992","unstructured":"Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1992)"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/363219.363232","volume":"12","author":"K. Paton","year":"1969","unstructured":"Paton, K.: An algorithm for finding a fundamental set of cycles of a graph. Comm. ACM\u00a012, 514\u2013519 (1969)","journal-title":"Comm. ACM"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1002\/jgt.3190130115","volume":"13","author":"D. Hartvigsen","year":"1989","unstructured":"Hartvigsen, D., Zemel, E.: Is every cycle basis fundamental? J. Graph Theory\u00a013, 117\u2013137 (1989)","journal-title":"Graph Theory"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/355984.355988","volume":"8","author":"N. Deo","year":"1982","unstructured":"Deo, N., Prabhu, G., Krishnamoorthy, M.: Algorithms for generating fundamental cycles in a graph. ACM Trans. Math. Softw.\u00a08, 26\u201342 (1982)","journal-title":"ACM Trans. Math. Softw."},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00453-004-1098-x","volume":"40","author":"F. Berger","year":"2004","unstructured":"Berger, F., Gritzmann, P., de Vries, S.: Minimum cycle bases for network graphs. Algorithmica\u00a040, 51\u201362 (2004)","journal-title":"Algorithmica"},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1016\/j.endm.2005.06.092","volume":"22","author":"J. Horton","year":"2005","unstructured":"Horton, J., Berger, F.: Minimum cycle bases of graphs over different fields. Electronic Notes in Discrete Mathematics\u00a022, 501\u2013505 (2005)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.ipl.2005.01.006","volume":"94","author":"C. Liebchen","year":"2005","unstructured":"Liebchen, C., Rizzi, R.: A greedy approach to compute a minimum cycle basis of a directed graph. Information Processing Letters\u00a094, 107\u2013112 (2005)","journal-title":"Information Processing Letters"},{"key":"2_CR10","unstructured":"Hubicka, E., Sys\u0142o, M.: Minimal bases of cycles of a graph. In: Fiedler, M. (ed.) Recent Advances in Graph Theory, Proc. 2nd Czechoslovak Conference on Graph Theory, Academia, pp. 283\u2013293 (1975)"},{"key":"2_CR11","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1021\/c160040a013","volume":"11","author":"M. Plotkin","year":"1971","unstructured":"Plotkin, M.: Mathematical basis of ring-finding algorithms in CIDS. J. Chem. Documentation\u00a011, 60\u201363 (1971)","journal-title":"J. Chem. Documentation"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1137\/0216026","volume":"16","author":"J. Horton","year":"1987","unstructured":"Horton, J.: A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput.\u00a016, 358\u2013366 (1987)","journal-title":"SIAM J. Comput."},{"key":"2_CR13","doi-asserted-by":"crossref","first-page":"9","DOI":"10.37236\/1294","volume":"4","author":"P. Vismara","year":"1997","unstructured":"Vismara, P.: Union of all the minimum cycle bases of a graph. Electronic J. Comb.\u00a04, R9 (1997)","journal-title":"Electronic J. Comb."},{"key":"2_CR14","unstructured":"de Pina, J.: Applications of shortest path methods. Ph.D thesis, University of Amsterdam, The Netherlands (2002)"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-45471-3_21","volume-title":"Algorithm Theory - SWAT 2002","author":"A. Golynski","year":"2002","unstructured":"Golynski, A., Horton, J.D.: A polynomial time algorithm to find the minimum cycle basis of a regular matroid. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol.\u00a02368, p. 200. Springer, Heidelberg (2002)"},{"key":"2_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1007\/978-3-540-27836-8_71","volume-title":"Automata, Languages and Programming","author":"T. Kavitha","year":"2004","unstructured":"Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.: A faster algorithm for minimum cycle bases of graphs. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 846\u2013857. Springer, Heidelberg (2004)"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Michail, D.: Minimum cycle bases: Faster and simpler. ACM Trans. Algorithms (2009) (to appear)","DOI":"10.1145\/1644015.1644023"},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/s00224-006-1319-6","volume":"40","author":"T. Kavitha","year":"2007","unstructured":"Kavitha, T., Mehlhorn, K.: Algorithms to compute minimum cycle basis in directed graphs. Theory of Computing Systems\u00a040, 485\u2013505 (2007)","journal-title":"Theory of Computing Systems"},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1002\/jgt.3190150408","volume":"15","author":"D. Hartvigsen","year":"1991","unstructured":"Hartvigsen, D., Mardon, R.: The prism-free planar graphs and their cycles bases. J. Graph Theory\u00a015, 431\u2013441 (1991)","journal-title":"J. Graph Theory"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Berger, F.: Minimum cycle bases in graphs. Ph.D thesis, TU M\u00fcnchen (2004)","DOI":"10.1007\/s00453-004-1098-x"},{"key":"2_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-540-24838-5_2","volume-title":"Experimental and Efficient Algorithms","author":"E. Amaldi","year":"2004","unstructured":"Amaldi, E., Liberti, L., Maculan, N., Maffioli, F.: Efficient edge-swapping heuristics for finding minimum fundamental cycle bases. In: Ribeiro, C.C., Martins, S.L. (eds.) WEA 2004. LNCS, vol.\u00a03059, pp. 14\u201329. Springer, Heidelberg (2004)"},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1006\/jctb.1993.1008","volume":"57","author":"D. Hartvigsen","year":"1993","unstructured":"Hartvigsen, D., Mardon, R.: When do short cycles generate the cycle space? J. Comb. Theory, Ser. B\u00a057, 88\u201399 (1993)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"2_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1007\/978-3-540-70918-3_44","volume-title":"STACS 2007","author":"T. Kavitha","year":"2007","unstructured":"Kavitha, T., Mehlhorn, K., Michail, D.: New approximation algorithms for minimum cycle bases of graphs. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 512\u2013523. Springer, Heidelberg (2007)"},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"1430","DOI":"10.1137\/060670730","volume":"38","author":"R. Hariharan","year":"2008","unstructured":"Hariharan, R., Kavitha, T., Mehlhorn, K.: Faster deterministic and randomized algorithms for minimum cycle basis in directed graphs. SIAM J. Comp.\u00a038, 1430\u20131447 (2008)","journal-title":"SIAM J. Comp."},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.dam.2006.06.007","volume":"55","author":"C. Liebchen","year":"2007","unstructured":"Liebchen, C., Rizzi, R.: Classes of cycle bases. Discrete Appl. Math.\u00a055, 337\u2013355 (2007)","journal-title":"Discrete Appl. Math."},{"key":"2_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/978-3-540-24592-6_12","volume-title":"Approximation and Online Algorithms","author":"G. Galbiati","year":"2004","unstructured":"Galbiati, G., Amaldi, E.: On the approximability of the minimum fundamental cycle basis problem. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol.\u00a02909, pp. 151\u2013164. Springer, Heidelberg (2004)"},{"key":"2_CR27","doi-asserted-by":"crossref","unstructured":"Rizzi, R.: Minimum weakly fundamental cycle bases are hard to find. Algorithmica (2009), doi:10.1007\/s00453\u2013007\u20139112\u20138","DOI":"10.1007\/s00453-007-9112-8"},{"key":"2_CR28","doi-asserted-by":"publisher","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.: New length bounds for cycle bases. Information Processing Letters\u00a0104, 186\u2013193 (2007)","journal-title":"Information Processing Letters"},{"key":"2_CR29","series-title":"Advanced series in electrical and computer engineering","doi-asserted-by":"publisher","DOI":"10.1142\/0859","volume-title":"Active Network Analysis","author":"W.K. Chen","year":"1991","unstructured":"Chen, W.K.: Active Network Analysis. Advanced series in electrical and computer engineering, vol.\u00a02. World Scientific, Singapore (1991)"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1109\/TCT.1971.1083223","volume":"18","author":"G. Hachtel","year":"1971","unstructured":"Hachtel, G., Brayton, R., Gustavson, F.: The sparse tableau approach to network analysis and design. IEEE Transactions of Circuit Theory\u00a0CT-18, 111\u2013113 (1971)","journal-title":"IEEE Transactions of Circuit Theory"},{"key":"2_CR31","unstructured":"Est\u00e9vez-Schwarz, D., Feldmann, U.: Diagnosis of erroneous circuit descriptions. Slides of a presentation, Paderborn (March 2003)"},{"key":"2_CR32","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1021\/ci00063a007","volume":"29","author":"G.M. Downs","year":"1989","unstructured":"Downs, G.M., Gillet, V.J., Holliday, J.D., Lynch, M.F.: Review of ring perception algorithms for chemical graphs. J. Chem. Inf. Comput. Sci.\u00a029, 172\u2013187 (1989)","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"2_CR33","doi-asserted-by":"crossref","first-page":"16","DOI":"10.37236\/1494","volume":"7","author":"P. Gleiss","year":"2000","unstructured":"Gleiss, P., Leydold, J., Stadler, P.: Interchangeability of relevant cycles in graphs. Electronic J. Comb.\u00a07, R16 (2000)","journal-title":"Electronic J. Comb."},{"key":"2_CR34","unstructured":"Berger, F., Gritzmann, P., de Vries, S.: Computing cyclic invariants for molecular graphs (2008) (manuscript)"},{"key":"2_CR35","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1137\/0402049","volume":"2","author":"P. Serafini","year":"1989","unstructured":"Serafini, P., Ukovich, W.: A mathematical model for periodic scheduling problems. SIAM J. Discrete Math.\u00a02, 550\u2013581 (1989)","journal-title":"SIAM J. Discrete Math."},{"key":"2_CR36","unstructured":"Odijk, M.: Railway timetable generation. Ph.D thesis, TU Delft, The Netherlands (1997)"},{"key":"2_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(95)00073-Z","volume":"69","author":"K. Nachtigall","year":"1996","unstructured":"Nachtigall, K.: Periodic network optimization with different arc frequencies. Discrete Appl. Math.\u00a069, 1\u201317 (1996)","journal-title":"Discrete Appl. Math."},{"key":"2_CR38","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1016\/S0377-2217(96)00284-6","volume":"103","author":"K. Nachtigall","year":"1997","unstructured":"Nachtigall, K., Voget, S.: Minimizing waiting times in integrated fixed interval timetables by upgrading railway tracks. Europ. J. Oper. Res.\u00a0103, 610\u2013627 (1997)","journal-title":"Europ. J. Oper. Res."},{"key":"2_CR39","doi-asserted-by":"crossref","unstructured":"Liebchen, C., M\u00f6hring, R.: A case study in periodic timetabling. In: Proceedings of ATMOS 2002. Elec. Notes in Theor. Comput. Sci (ENTS), vol.\u00a066.6 (2002)","DOI":"10.1016\/S1571-0661(04)80526-7"},{"key":"2_CR40","doi-asserted-by":"crossref","unstructured":"Liebchen, C., Proksch, M., Wagner, F.: Performance of algorithms for periodic timetable optimization. In: Computer-aided Systems in Public Transport. Lect. Notes in Economics and Mathematical System, vol.\u00a0600, pp. 151\u2013180 (2008)","DOI":"10.1007\/978-3-540-73312-6_8"},{"key":"2_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/978-3-540-39658-1_64","volume-title":"Algorithms - ESA 2003","author":"C. Liebchen","year":"2003","unstructured":"Liebchen, C.: Finding short integral cycle bases for cyclic timetabling. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 715\u2013726. Springer, Heidelberg (2003)"},{"key":"2_CR42","doi-asserted-by":"crossref","unstructured":"Liebchen, C., M\u00f6hring, R.: The modeling power of the periodic event scheduling problem: railway timetables \u2013 and beyond. In: Computer-aided Systems in Public Transport, pp. 117\u2013150 (2008)","DOI":"10.1007\/978-3-540-73312-6_7"},{"key":"2_CR43","unstructured":"Kaminski, A.: Erzeugung und Optimierung zyklischer Zeitpl\u00e4ne. Diploma Thesis (in German), TU M\u00fcnchen (2004)"}],"container-title":["Lecture Notes in Computer Science","Algorithmics of Large and Complex Networks"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02094-0_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T02:42:10Z","timestamp":1589942530000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02094-0_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642020933","9783642020940"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02094-0_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}