{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:22:31Z","timestamp":1775874151865,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,10,13]],"date-time":"2007-10-13T00:00:00Z","timestamp":1192233600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/2.0"},{"start":{"date-parts":[[2007,10,13]],"date-time":"2007-10-13T00:00:00Z","timestamp":1192233600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,11]]},"DOI":"10.1007\/s00453-007-9064-z","type":"journal-article","created":{"date-parts":[[2007,10,12]],"date-time":"2007-10-12T17:56:40Z","timestamp":1192211800000},"page":"333-349","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["An $\\tilde{O}(m^{2}n)$ Algorithm for Minimum Cycle Basis of\u00a0Graphs"],"prefix":"10.1007","volume":"52","author":[{"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios","family":"Michail","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katarzyna E.","family":"Paluch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,10,13]]},"reference":[{"key":"9064_CR1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1098\/rspa.1976.0095","volume":"350","author":"A.C. Cassell","year":"1976","unstructured":"Cassell, A.C., Henderson, J.C., Ramachandran, K.: Cycle bases of minimal measure for the structural analysis of skeletal structures by the flexibility method. Proc. R. Soc. Lond. Ser. A 350, 61\u201370 (1976)","journal-title":"Proc. R. Soc. Lond. Ser. A"},{"key":"9064_CR2","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1109\/TCT.1973.1083752","volume":"20","author":"L.O. Chua","year":"1973","unstructured":"Chua, L.O., Chen, L.: On optimally sparse cycle and coboundary basis for a linear graph. IEEE Trans. Circuit Theory 20, 495\u2013503 (1973)","journal-title":"IEEE Trans. Circuit Theory"},{"key":"9064_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.2000.1117","volume":"38","author":"E. Cohen","year":"2001","unstructured":"Cohen, E., Zwick, U.: All-pairs small-stretch paths. J. Algorithms 38, 335\u2013353 (2001)","journal-title":"J. Algorithms"},{"key":"9064_CR4","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 multiplications via arithmetic progressions. J. Symb. Comput. 9, 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"9064_CR5","unstructured":"de Pina, J.C.: Applications of shortest path methods. PhD thesis, University of Amsterdam, Netherlands (1995)"},{"key":"9064_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.M., Krishnamoorthy, M.S.: Algorithms for generating fundamental cycles in a graph. ACM Trans. Math. Softw. 8, 26\u201342 (1982)","journal-title":"ACM Trans. Math. Softw."},{"key":"9064_CR7","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1006\/jcss.1997.1385","volume":"54","author":"Z. Galil","year":"1997","unstructured":"Galil, Z., Margalit, O.: All pairs shortest paths for graphs with small integer length edges. J. Comput. Syst. Sci. 54, 243\u2013254 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9064_CR8","doi-asserted-by":"crossref","unstructured":"Golynski, A., Horton, J.D.: A polynomial time algorithm to find the minimum cycle basis of a regular matroid. In: 8th Scandinavian Workshop on Algorithm Theory (2002)","DOI":"10.1007\/3-540-45471-3_21"},{"issue":"1","key":"9064_CR9","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1006\/jagm.1993.1033","volume":"15","author":"D. Hartvigsen","year":"1993","unstructured":"Hartvigsen, D.: Minimum path bases. J. Algorithms 15(1), 125\u2013142 (1993)","journal-title":"J. Algorithms"},{"key":"9064_CR10","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 57, 88\u201399 (1993)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"3","key":"9064_CR11","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. J. Discret. Math. 7(3), 403\u2013418 (1994)","journal-title":"J. Discret. Math."},{"key":"9064_CR12","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/0216026","volume":"16","author":"J.D. Horton","year":"1987","unstructured":"Horton, J.D.: A polynomial-time algorithm to find a shortest cycle basis of a graph. SIAM J. Comput. 16, 359\u2013366 (1987)","journal-title":"SIAM J. Comput."},{"key":"9064_CR13","unstructured":"Hubicka, E., Syslo, M.M.: Minimal bases of cycles of a graph. Recent Adv. Graph. Theory, 283\u2013293 (1975)"},{"key":"9064_CR14","unstructured":"Kavitha, T., Mehlhorn, K., Michail, D.: New approximation algorithms for minimum cycle bases of graphs. In: Proceedings of 24th International Symposium on Theoretical Aspects of Computer Science (STACS) (2007)"},{"key":"9064_CR15","first-page":"631","volume":"16","author":"E. Kolasinska","year":"1980","unstructured":"Kolasinska, E.: On a minimum cycle basis of a graph. Zastos. Mat. 16, 631\u2013639 (1980)","journal-title":"Zastos. Mat."},{"key":"9064_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/11427186_5","volume-title":"Proceedings of 4th International Workshop on Experimental and Efficient Algorithms","author":"K. Mehlhorn","year":"2005","unstructured":"Mehlhorn, K., Michail, D.: Implementing minimum cycle basis algorithms. In: Proceedings of 4th International Workshop on Experimental and Efficient Algorithms. Lecture Notes in Computer Science, vol. 3503, pp. 32\u201343. Springer, New York (2005)"},{"key":"9064_CR17","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"M.W. Padberg","year":"1982","unstructured":"Padberg, M.W., Rao, M.R.: Odd minimum cut-sets and b-matchings. Math. Oper. Res. 7, 67\u201380 (1982)","journal-title":"Math. Oper. Res."},{"key":"9064_CR18","unstructured":"Pettie, S., Ramachandran, V.: Computing shortest paths with comparisons and additions. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 267\u2013276 (2002)"},{"key":"9064_CR19","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R. Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51, 400\u2013403 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9064_CR20","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. 19, 171\u2013175 (1964)","journal-title":"Uspekhi Mat. Nauk."},{"issue":"6","key":"9064_CR21","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1016\/j.cag.2006.08.019","volume":"30","author":"G. Tewari","year":"2006","unstructured":"Tewari, G., Gotsman, C., Gortler, S.J.: Meshing genus-1 point clouds using discrete one-forms. Comput. Graph. 30(6), 917\u2013926 (2006)","journal-title":"Comput. Graph."},{"key":"9064_CR22","first-page":"362","volume":"46","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J.\u00a0ACM 46, 362\u2013394 (1999)","journal-title":"J.\u00a0ACM"},{"key":"9064_CR23","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1006\/jagm.2000.1080","volume":"35","author":"M. Thorup","year":"2000","unstructured":"Thorup, M.: Floats, integers, and single source shortest paths. J. Algorithms 35, 189\u2013201 (2000)","journal-title":"J. Algorithms"},{"key":"9064_CR24","doi-asserted-by":"crossref","unstructured":"Zwick, U.: All pairs shortest paths in weighted directed graphs\u2014exact and approximate algorithms. In: Proceedings of the 39th Annual IEEE FOCS, pp. 310\u2013319 (1998)","DOI":"10.1109\/SFCS.1998.743464"},{"key":"9064_CR25","volume-title":"Theory of Finite Graphs","author":"A.A. Zykov","year":"1969","unstructured":"Zykov, A.A.: Theory of Finite Graphs. Nauka, Novosibirsk (1969)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9064-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-007-9064-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9064-z.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9064-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T16:56:39Z","timestamp":1737478599000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-007-9064-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,13]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["9064"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9064-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,13]]},"assertion":[{"value":"22 February 2006","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2007","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2007","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}