{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,6]],"date-time":"2026-02-06T04:46:27Z","timestamp":1770353187991,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642130359","type":"print"},{"value":"9783642130366","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13036-6_30","type":"book-chapter","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T08:36:09Z","timestamp":1275986169000},"page":"397-410","source":"Crossref","is-referenced-by-count":10,"title":["Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs"],"prefix":"10.1007","author":[{"given":"Edoardo","family":"Amaldi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claudio","family":"Iuliano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-642-04128-0_28","volume-title":"Algorithms - ESA 2009","author":"E. Amaldi","year":"2009","unstructured":"Amaldi, E., Iuliano, C., Jurkiewicz, T., Mehlhorn, K., Rizzi, R.: Breaking the O(m 2 n) barrier for minimum cycle bases. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 301\u2013312. Springer, Heidelberg (2009)"},{"issue":"12","key":"30_CR2","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00186-008-0255-4","volume":"69","author":"E. Amaldi","year":"2009","unstructured":"Amaldi, E., Liberti, L., Maculan, N., Maffioli, F.: Edge-swapping algorithms for the minimum fundamental cycle basis problem. Mathematical Methods of Operations Research\u00a069(12), 205\u2013233 (2009)","journal-title":"Mathematical Methods of Operations Research"},{"issue":"3","key":"30_CR3","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V. Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math.\u00a012(3), 289\u2013297 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"30_CR4","unstructured":"Bollobas, B.: Graduate Texts in Mathematics, vol.\u00a0184. Springer, Heidelberg (2nd printing)"},{"issue":"1-3","key":"30_CR5","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0166-218X(99)00180-8","volume":"101","author":"L. Brunetta","year":"2000","unstructured":"Brunetta, L., Maffioli, F., Trubian, M.: Solving the feedback vertex set problem on undirected graphs. Discrete Applied Mathematics\u00a0101(1-3), 37\u201351 (2000)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"30_CR6","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput.\u00a09(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"30_CR7","unstructured":"De Pina, J.C.: Applications of shortest path methods. Ph.D. thesis, University of Amsterdam, The Netherlands (1995)"},{"issue":"1","key":"30_CR8","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.S.: Algorithms for generating fundamental cycles in a graph. ACM Trans. on Mathematical Software\u00a08(1), 26\u201342 (1982)","journal-title":"ACM Trans. on Mathematical Software"},{"key":"30_CR9","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P. Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s, P., R\u00e9nyi, A.: On random graphs, I. Publicationes Mathematicae (Debrecen)\u00a06, 290\u2013297 (1959)","journal-title":"Publicationes Mathematicae (Debrecen)"},{"key":"30_CR10","unstructured":"Gleiss, P.M.: Short cycles: minimum cycle bases of graphs from chemistry and biochemistry. Ph.D. thesis, Universit\u00e4t Wien, Austria (2001)"},{"key":"30_CR11","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, pp. 200\u2013209. Springer, Heidelberg (2002)"},{"issue":"3","key":"30_CR12","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/S0895480190177042","volume":"7","author":"D. Hartvigsen","year":"1994","unstructured":"Hartvigsen, D., Mardon, R.: The all-pairs min cut problem and the minimum cycle basis problem on planar graphs. SIAM J. Discrete Math.\u00a07(3), 403\u2013418 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"30_CR13","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1137\/0216026","volume":"16","author":"J.D. Horton","year":"1987","unstructured":"Horton, J.D.: A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Computing\u00a016(2), 358\u2013366 (1987)","journal-title":"SIAM J. Computing"},{"issue":"4","key":"30_CR14","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.cosrev.2009.08.001","volume":"3","author":"T. Kavitha","year":"2009","unstructured":"Kavitha, T., Liebchen, C., Mehlhorn, K., Michail, D., Rizzi, R., Ueckerdt, T., Zweig, K.A.: Cycle bases in graphs characterization, algorithms, complexity, and applications. Computer Science Review\u00a03(4), 199\u2013243 (2009)","journal-title":"Computer Science Review"},{"issue":"3","key":"30_CR15","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s00453-007-9064-z","volume":"52","author":"T. Kavitha","year":"2008","unstructured":"Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.E.: An $\\tilde{O}(m^2 n)$ algorithm for minimum cycle basis of graphs. Algorithmica\u00a052(3), 333\u2013349 (2008)","journal-title":"Algorithmica"},{"issue":"3","key":"30_CR16","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.dam.2006.06.007","volume":"155","author":"C. Liebchen","year":"2007","unstructured":"Liebchen, C., Rizzi, R.: Classes of cycle bases. Discrete Applied Mathematics\u00a0155(3), 337\u2013355 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"30_CR17","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Michail, D.: Implementing minimum cycle basis algorithms. ACM Journal of Experimental Algorithmics\u00a011 (2006)","DOI":"10.1145\/1187436.1216582"},{"key":"30_CR18","unstructured":"Mehlhorn, K., Michail, D.: Minimum cycle bases: Faster and simpler. Accepted for publication in ACM Trans. on Algorithms (2007)"},{"key":"30_CR19","volume-title":"LEDA: A Platform for Combinatorial and Geometric Computing","author":"K. Mehlhorn","year":"1999","unstructured":"Mehlhorn, K., N\u00e4her, S.: LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (1999)"},{"issue":"3","key":"30_CR20","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/s00453-007-9112-8","volume":"53","author":"R. Rizzi","year":"2009","unstructured":"Rizzi, R.: Minimum weakly fundamental cycle bases are hard to find. Algorithmica\u00a053(3), 402\u2013424 (2009)","journal-title":"Algorithmica"},{"key":"30_CR21","first-page":"171","volume":"19","author":"G.F. Stepanec","year":"1964","unstructured":"Stepanec, G.F.: Basis systems of vector cycles with extremal properties in graphs. Uspekhi Mat. Nauk II\u00a019, 171\u2013175 (1964) (in Russian)","journal-title":"Uspekhi Mat. Nauk II"},{"key":"30_CR22","volume-title":"Theory of Finite Graphs","author":"A.A. Zykov","year":"1969","unstructured":"Zykov, A.A.: Theory of Finite Graphs. Nauka, Novosibirsk (1969) (in Russian)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13036-6_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T09:23:42Z","timestamp":1685611422000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13036-6_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642130359","9783642130366"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13036-6_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}