{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,12]],"date-time":"2026-07-12T04:55:33Z","timestamp":1783832133889,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_71","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T22:53:21Z","timestamp":1284591201000},"page":"846-857","source":"Crossref","is-referenced-by-count":34,"title":["A Faster Algorithm for Minimum Cycle Basis of Graphs"],"prefix":"10.1007","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"}]},{"given":"Katarzyna","family":"Paluch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"71_CR1","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":"71_CR2","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1109\/TCT.1973.1083752","volume":"CT-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\u00a0CT-20, 495\u2013503 (1973)","journal-title":"IEEE Trans. Circuit Theory"},{"key":"71_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. Journal of Algorithms\u00a038, 335\u2013353 (2001)","journal-title":"Journal of Algorithms"},{"key":"71_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. Journal of Symb. Comput.\u00a09, 251\u2013280 (1990)","journal-title":"Journal of Symb. Comput."},{"key":"71_CR5","unstructured":"de Pina, J.C.: Applications of Shortest Path Methods. PhD thesis, University of Amsterdam, Netherlands (1995)"},{"key":"71_CR6","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. Journal of Computing Systems and Sciences\u00a054, 243\u2013254 (1997)","journal-title":"Journal of Computing Systems and Sciences"},{"key":"71_CR7","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"},{"key":"71_CR8","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":"71_CR9","unstructured":"Hubicka, E., Syslo, M.M.: Minimal bases of cycles of a graph. In: Fiedler, M. (ed.) Recent Advances in Graph Theory, pp. 283\u2013293 (1975)"},{"key":"71_CR10","first-page":"631","volume":"16","author":"E. Kolasinska","year":"1980","unstructured":"Kolasinska, E.: On a minimum cycle basis of a graph. Zastos. Mat.\u00a016, 631\u2013639 (1980)","journal-title":"Zastos. Mat."},{"key":"71_CR11","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"Rao Padberg","year":"1982","unstructured":"Padberg, Rao. Odd minimum cut-sets and b-matchings. Mathematics of Operations Research 7, 67\u201380 (1982)","journal-title":"Mathematics of Operations Research"},{"key":"71_CR12","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. Journal of Computing Systems and Sciences\u00a051, 400\u2013403 (1995)","journal-title":"Journal of Computing Systems and Sciences"},{"key":"71_CR13","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":"71_CR14","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM\u00a046, 362\u2013394 (1999)","journal-title":"Journal of the ACM"},{"key":"71_CR15","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. Journal of Algorithms\u00a035, 189\u2013201 (2000)","journal-title":"Journal of Algorithms"},{"key":"71_CR16","doi-asserted-by":"crossref","unstructured":"Zwick, U.: All pairs shortest paths in weighted directed graphs - exact and approximate algorithms. In: Proc. of the 39th Annual IEEE FOCS, pp. 310\u2013319 (1998)","DOI":"10.1109\/SFCS.1998.743464"},{"key":"71_CR17","unstructured":"Zykov, A.A.: Theory of Finite Graphs. Nauka, Novosibirsk (1969)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_71.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T21:30:52Z","timestamp":1740519052000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}