{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:22Z","timestamp":1725511762632},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_44","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T19:41:23Z","timestamp":1179949283000},"page":"512-523","source":"Crossref","is-referenced-by-count":7,"title":["New Approximation Algorithms for Minimum Cycle Bases of Graphs"],"prefix":"10.1007","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"}]}],"member":"297","reference":[{"key":"44_CR1","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\u00a019, 171\u2013175 (1964)","journal-title":"Uspekhi Mat. Nauk"},{"key":"44_CR2","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 Journal of Computing\u00a016, 359\u2013366 (1987)","journal-title":"SIAM Journal of Computing"},{"key":"44_CR3","unstructured":"de Pina, J.: Applications of Shortest Path Methods. PhD thesis, University of Amsterdam, Netherlands (1995)"},{"key":"44_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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, Springer, Heidelberg (2002)"},{"issue":"1","key":"44_CR5","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 basis for network graphs. Algorithmica\u00a040(1), 51\u201362 (2004)","journal-title":"Algorithmica"},{"key":"44_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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., et al.: A faster algorithm for minimum cycle basis of graphs. In: D\u00edaz, J., et al. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 846\u2013857. Springer, Heidelberg (2004)"},{"key":"44_CR7","unstructured":"Huber, M.: Implementation of algorithms for sparse cycle bases of graphs. Technical report, Technische Universit\u00e4t M\u00fcnchen (2002), \n                    \n                      http:\/\/www-m9.ma.tum.de\/dm\/cycles\/mhuber"},{"key":"44_CR8","unstructured":"Kreisbasenbibliothek CyBaL (2004), \n                    \n                      http:\/\/www-m9.ma.tum.de\/dm\/cycles\/cybal"},{"key":"44_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/11427186_5","volume-title":"Experimental and Efficient Algorithms","author":"K. Mehlhorn","year":"2005","unstructured":"Mehlhorn, K., Michail, D.: Implementing minimum cycle basis algorithms. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol.\u00a03503, pp. 32\u201343. Springer, Heidelberg (2005)"},{"key":"44_CR10","volume-title":"Graphs, Networks, and Algorithms","author":"M.N.S. Swamy","year":"1981","unstructured":"Swamy, M.N.S., Thulasiraman, K.: Graphs, Networks, and Algorithms. John Wiley & Sons, New York (1981)"},{"key":"44_CR11","doi-asserted-by":"publisher","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. Royal Society of London Series A\u00a0350, 61\u201370 (1976)","journal-title":"Proc. Royal Society of London Series A"},{"key":"44_CR12","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":"44_CR13","doi-asserted-by":"crossref","unstructured":"Tewari, G., Gotsman, C., Gortler, S.J.: Meshing genus-1 point clouds using discrete one-forms. Computers and Graphics, to appear (2006)","DOI":"10.1016\/j.cag.2006.08.019"},{"key":"44_CR14","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. Journal of Symb. Comput.\u00a09, 251\u2013280 (1990)","journal-title":"Journal of Symb. Comput."},{"key":"44_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1007\/978-3-540-31856-9_54","volume-title":"STACS 2005","author":"T. Kavitha","year":"2005","unstructured":"Kavitha, T., Mehlhorn, K.: A polynomial time algorithm for minimum cycle basis in directed graphs. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 654\u2013665. Springer, Heidelberg (2005)"},{"issue":"3","key":"44_CR16","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. Inf. Process. Lett.\u00a094(3), 107\u2013112 (2005)","journal-title":"Inf. Process. Lett."},{"key":"44_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/11786986_23","volume-title":"Automata, Languages and Programming","author":"R. Hariharan","year":"2006","unstructured":"Hariharan, R., Kavitha, T., Mehlhorn, K.: A faster deterministic algorithm for minimum cycle basis in directed graphs. In: Bugliesi, M., et al. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 250\u2013261. Springer, Heidelberg (2006)"},{"key":"44_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/11523468_23","volume-title":"Automata, Languages and Programming","author":"T. Kavitha","year":"2005","unstructured":"Kavitha, T.: An \u00d5(m\n                           2\n                           n) randomized algorithm to compute a minimum cycle basis of a directed graph. In: Caires, L., et al. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 273\u2013284. Springer, Heidelberg (2005)"},{"issue":"1","key":"44_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., et al.: On sparse spanners of weighted graphs. Discrete Comput. Geom.\u00a09(1), 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"44_CR20","first-page":"183","volume-title":"ACM Symposium on Theory of Computing","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In: ACM Symposium on Theory of Computing, pp. 183\u2013192. ACM Press, New York (2001)"},{"key":"44_CR21","first-page":"1","volume-title":"Proceedings of 13th ACM Symposium on Parallel Algorithms and Architecture","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of 13th ACM Symposium on Parallel Algorithms and Architecture, pp. 1\u201310. ACM Press, New York (2001)"},{"key":"44_CR22","volume-title":"Introduction to Analytic Number Theory","author":"T.M. Apostol","year":"1997","unstructured":"Apostol, T.M.: Introduction to Analytic Number Theory. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_44.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:11:56Z","timestamp":1605744716000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_44","relation":{},"subject":[]}}