{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:08Z","timestamp":1750281788764},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642041273"},{"type":"electronic","value":"9783642041280"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04128-0_28","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"301-312","source":"Crossref","is-referenced-by-count":12,"title":["Breaking the O(m 2 n) Barrier for Minimum Cycle Bases"],"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":"Tomasz","family":"Jurkiewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"28_CR1","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 bases for network graphs. Algorithmica\u00a040(1), 51\u201362 (2004)","journal-title":"Algorithmica"},{"key":"28_CR2","unstructured":"De Pina, J.C.: Applications of shortest path methods. PhD thesis, University of Amsterdam, The Netherlands (1995)"},{"issue":"6","key":"28_CR3","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G.N. Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Computing\u00a016(6), 1004\u20131022 (1987)","journal-title":"SIAM J. Computing"},{"key":"28_CR4","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":"4","key":"28_CR5","doi-asserted-by":"publisher","first-page":"1430","DOI":"10.1137\/060670730","volume":"38","author":"R. Hariharan","year":"2008","unstructured":"Hariharan, R., Kavitha, T., Mehlhorn, K.: Faster deterministic and randomized algorithms for minimum cycle basis in directed graphs. SIAM J. Computing\u00a038(4), 1430\u20131447 (2008)","journal-title":"SIAM J. Computing"},{"issue":"3","key":"28_CR6","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":"28_CR7","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"},{"key":"28_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/11523468_23","volume-title":"Automata, Languages and Programming","author":"T. Kavitha","year":"2005","unstructured":"Kavitha, T.: An $\\tilde{O}(m^2 n)$ randomized algorithm to compute a minimum cycle basis of a directed graph. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 273\u2013284. Springer, Heidelberg (2005)"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"Kavitha, T., Liebchen, C., Mehlhorn, K., Michail, D., Rizzi, R., Ueckerdt, T., Zweig, K.: Cycle bases in graphs: Characterization, algorithms, complexity, and applications, 78 pages (submitted for publication) (March 2009)","DOI":"10.1016\/j.cosrev.2009.08.001"},{"issue":"4","key":"28_CR10","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/s00224-006-1319-6","volume":"40","author":"T. Kavitha","year":"2007","unstructured":"Kavitha, T., Mehlhorn, K.: Algorithms to compute minimum cycle basis in directed graphs. Theory of Computing Systems\u00a040(4), 485\u2013505 (2007); A preliminary version of this paper appeared in STACS 2005, vol. 3404, pp. 654\u2013665","journal-title":"Theory of Computing Systems"},{"issue":"3","key":"28_CR11","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); A preliminary version of this paper appeared in ICALP 2004, vol. 3142, pp. 846\u2013857","journal-title":"Algorithmica"},{"issue":"3","key":"28_CR12","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. Information Processing Letters\u00a094(3), 107\u2013112 (2005)","journal-title":"Information Processing Letters"},{"issue":"3","key":"28_CR13","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":"28_CR14","unstructured":"Mehlhorn, K., Michail, D.: Minimum cycle bases: Faster and simpler. Accepted for publication in ACM Transactions on Algorithms (2007)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T15:22:09Z","timestamp":1558538529000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}