{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,12]],"date-time":"2026-07-12T04:55:34Z","timestamp":1783832134106,"version":"3.55.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,5,20]],"date-time":"2009-05-20T00:00:00Z","timestamp":1242777600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,4]]},"DOI":"10.1007\/s00453-009-9313-4","type":"journal-article","created":{"date-parts":[[2009,5,19]],"date-time":"2009-05-19T17:57:37Z","timestamp":1242755857000},"page":"471-488","source":"Crossref","is-referenced-by-count":5,"title":["New Approximation Algorithms for Minimum Cycle Bases of Graphs"],"prefix":"10.1007","volume":"59","author":[{"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dimitrios","family":"Michail","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,5,20]]},"reference":[{"issue":"1","key":"9313_CR1","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer,\u00a0I., Das,\u00a0G., Dobkin,\u00a0D., Joseph,\u00a0D., Soares,\u00a0J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9(1), 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9313_CR2","volume-title":"Introduction to Analytic Number Theory","author":"T.M. Apostol","year":"1997","unstructured":"Apostol, T.M.: Introduction to Analytic Number Theory. Springer, Berlin (1997)"},{"issue":"4","key":"9313_CR3","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1145\/1198513.1198518","volume":"2","author":"S. Baswana","year":"2006","unstructured":"Baswana,\u00a0S., Sen,\u00a0S.: Approximate distance oracles for unweighted graphs in expected o(n 2) time. ACM Trans. Algorithms 2(4), 557\u2013577 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9313_CR4","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s00453-004-1098-x","volume":"40","author":"F. Berger","year":"2004","unstructured":"Berger,\u00a0F., Gritzmann,\u00a0P., de Vries,\u00a0S.: Minimum cycle basis for network graphs. Algorithmica 40(1), 51\u201362 (2004)","journal-title":"Algorithmica"},{"issue":"1","key":"9313_CR5","first-page":"67","volume":"42","author":"P. Callahan","year":"1995","unstructured":"Callahan,\u00a0P., Kosaraju,\u00a0R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential field. J.\u00a0ACM 42(1), 67\u201390 (1995)","journal-title":"J.\u00a0ACM"},{"key":"9313_CR6","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,\u00a0K.: Cycle bases of minimal measure for the structural analysis of skeletal structures by the flexibility method. Proc. R. Soc. Lond. Ser.\u00a0A 350, 61\u201370 (1976)","journal-title":"Proc. R. Soc. Lond. Ser.\u00a0A"},{"key":"9313_CR7","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith,\u00a0D., Winograd,\u00a0S.: Matrix multiplications via arithmetic progressions. J.\u00a0Symb. Comput. 9, 251\u2013280 (1990)","journal-title":"J.\u00a0Symb. Comput."},{"key":"9313_CR8","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1989","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press\/McGraw-Hill, Cambridge (1989)"},{"key":"9313_CR9","unstructured":"Kreisbasenbibliothek CyBaL: http:\/\/www-m9.ma.tum.de\/dm\/cycles\/cybal (2004)"},{"key":"9313_CR10","unstructured":"de Pina, J.C.: Applications of shortest path methods. PhD thesis, University of Amsterdam, The Netherlands (1995)"},{"key":"9313_CR11","unstructured":"Gleiss, P.M.: Short cycles, minimum cycle bases of graphs from chemistry and biochemistry. PhD thesis, Fakult\u00e4t F\u00fcr Naturwissenschaften und Mathematik der Universit\u00e4t Wien (2001)"},{"key":"9313_CR12","doi-asserted-by":"crossref","unstructured":"Golynski,\u00a0A., 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"},{"key":"9313_CR13","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1007\/11786986_23","volume-title":"ICALP 2006, 33rd International Colloquium on Automata, Languages and Programming","author":"R. Hariharan","year":"2006","unstructured":"Hariharan,\u00a0R., Kavitha,\u00a0T., Mehlhorn,\u00a0K.: A faster deterministic algorithm for minimum cycle basis in directed graphs. In: ICALP 2006, 33rd International Colloquium on Automata, Languages and Programming. LNCS, vol.\u00a04051, pp. 250\u2013261. Springer, Berlin (2006)"},{"issue":"3","key":"9313_CR14","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1137\/S0895480190177042","volume":"7","author":"D. Hartvigsen","year":"1994","unstructured":"Hartvigsen,\u00a0D., Mardon,\u00a0R.: The all-pairs min cut problem and the minimum cycle basis problem on planar graphs. J.\u00a0Discrete Math. 7(3), 403\u2013418 (1994)","journal-title":"J.\u00a0Discrete Math."},{"key":"9313_CR15","first-page":"549","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft,\u00a0J., Tarjan,\u00a0R.: Efficient planarity testing. J.\u00a0ACM 21, 549\u2013568 (1974)","journal-title":"J.\u00a0ACM"},{"key":"9313_CR16","doi-asserted-by":"crossref","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":"9313_CR17","unstructured":"Huber,\u00a0M.: Implementation of algorithms for sparse cycle bases of graphs. Technical report, Technische Universit\u00e4t M\u00fcnchen (2002). http:\/\/www-m9.ma.tum.de\/dm\/cycles\/mhuber"},{"key":"9313_CR18","series-title":"LNCS","first-page":"273","volume-title":"Proceedings of ICALP","author":"T. Kavitha","year":"2005","unstructured":"Kavitha,\u00a0T.: An $\\tilde{O}(m^{2}n)$ randomized algorithm to compute a minimum cycle basis of a directed graph. In: Proceedings of ICALP. LNCS, vol.\u00a03580, pp. 273\u2013284. Springer, Berlin (2005)"},{"issue":"4","key":"9313_CR19","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1007\/s00224-006-1319-6","volume":"40","author":"T. Kavitha","year":"2007","unstructured":"Kavitha,\u00a0T., Mehlhorn,\u00a0K.: Algorithms to compute minimum cycle basis in directed graphs. Theory Comput. Syst. 40(4), 485\u2013505 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9313_CR20","series-title":"LNCS","first-page":"512","volume-title":"STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science","author":"T. Kavitha","year":"2007","unstructured":"Kavitha,\u00a0T., Mehlhorn,\u00a0K., Michail,\u00a0D.: New approximation algorithms for minimum cycle bases of graphs. In: STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science. LNCS, vol.\u00a04393, pp. 512\u2013523. Springer, Berlin (2007)"},{"key":"9313_CR21","author":"T. Kavitha","year":"2007","unstructured":"Kavitha,\u00a0T., Mehlhorn,\u00a0K., Michail,\u00a0D., Paluch, K.E.: An $\\tilde{O}(m^{2}n)$ algorithm for minimum cycle basis of graphs. Algorithmica (2007). doi: 10.1007\/s00453-007-9064-z","journal-title":"Algorithmica"},{"key":"9313_CR22","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF02187821","volume":"7","author":"J.M. Keil","year":"1992","unstructured":"Keil, J.M., Gutwin, C.A.: Classes of graphs which approximate the complete euclidean graph. Discrete Comput. Geom. 7, 13\u201328 (1992)","journal-title":"Discrete Comput. Geom."},{"key":"9313_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.37236\/1354","volume":"5","author":"J. Leydold","year":"1998","unstructured":"Leydold,\u00a0J., Stadler, P.F.: Minimal cycle bases of outerplanar graphs. Electron. J. Combin. 5, 1\u201314 (1998)","journal-title":"Electron. J. Combin."},{"issue":"3","key":"9313_CR24","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.ipl.2005.01.006","volume":"94","author":"C. Liebchen","year":"2005","unstructured":"Liebchen,\u00a0C., Rizzi,\u00a0R.: A greedy approach to compute a minimum cycle basis of a directed graph. Inf. Process. Lett. 94(3), 107\u2013112 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9313_CR25","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.dam.2006.06.007","volume":"155","author":"C. Liebchen","year":"2007","unstructured":"Liebchen,\u00a0C., Rizzi,\u00a0R.: Classes of cycle bases. Discrete Appl. Math. 155(3), 337\u2013355 (2007)","journal-title":"Discrete Appl. Math."},{"key":"9313_CR26","first-page":"1","volume":"11","author":"K. Mehlhorn","year":"2006","unstructured":"Mehlhorn,\u00a0K., Michail,\u00a0D.: Implementing minimum cycle basis algorithms. J.\u00a0Exp. Algorithmics 11, 1\u201314 (2006)","journal-title":"J.\u00a0Exp. Algorithmics"},{"key":"9313_CR27","author":"R. Rizzi","year":"2007","unstructured":"Rizzi,\u00a0R.: Minimum weakly fundamental cycle bases are hard to find. Algorithmica (2007). doi: 10.1007\/s00453-007-9112-8","journal-title":"Algorithmica"},{"key":"9313_CR28","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/11523468_22","volume-title":"Proceedings of the 32nd International Colloquium in Automata, Languages and Programming","author":"L. Roditty","year":"2005","unstructured":"Roditty,\u00a0L., Thorup,\u00a0M., Zwick,\u00a0U.: Deterministic constructions of approximate distance oracles and spanners. In: Proceedings of the 32nd International Colloquium in Automata, Languages and Programming. LNCS, vol.\u00a03580, pp. 261\u2013272. Springer, Berlin (2005)"},{"key":"9313_CR29","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. Usp. Mat. Nauk 19, 171\u2013175 (1964)","journal-title":"Usp. Mat. Nauk"},{"key":"9313_CR30","volume-title":"Graphs, Networks, and Algorithms","author":"M.N.S. Swamy","year":"1981","unstructured":"Swamy, M.N.S., Thulasiraman,\u00a0K.: Graphs, Networks, and Algorithms. Wiley, New York (1981)"},{"issue":"6","key":"9313_CR31","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1016\/j.cag.2006.08.019","volume":"30","author":"G. Tewari","year":"2006","unstructured":"Tewari,\u00a0G., Gotsman,\u00a0C., Gortler, S.J.: Meshing genus-1 point clouds using discrete one-forms. Comput. Graph. 30(6), 917\u2013926 (2006)","journal-title":"Comput. Graph."},{"key":"9313_CR32","doi-asserted-by":"crossref","unstructured":"Thorup,\u00a0M., Zwick,\u00a0U.: Compact routing schemes. In: Proceedings of 13th ACM Symposium on Parallel Algorithms and Architecture, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"9313_CR33","first-page":"1","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup,\u00a0M., Zwick,\u00a0U.: Approximate distance oracles. J.\u00a0ACM 52(1), 1\u201324 (2005)","journal-title":"J.\u00a0ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9313-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9313-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9313-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T22:59:03Z","timestamp":1633474743000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9313-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,20]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["9313"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9313-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,20]]}}}