{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T00:54:59Z","timestamp":1750726499257,"version":"3.41.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T00:00:00Z","timestamp":1721779200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T00:00:00Z","timestamp":1721779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Prime Minister\u2019s Research Fellowship, MOE, Govt. of India","award":["0201883"],"award-info":[{"award-number":["0201883"]}]},{"name":"NSF","award":["CCF 2049010"],"award-info":[{"award-number":["CCF 2049010"]}]},{"name":"Science and Engineering Research Board, Department of Science and Technology","award":["CRG\/2021\/005278"],"award-info":[{"award-number":["CRG\/2021\/005278"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s00454-024-00680-8","type":"journal-article","created":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T19:01:54Z","timestamp":1721847714000},"page":"49-77","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast Algorithms for Minimum Homology Basis"],"prefix":"10.1007","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-3215-644X","authenticated-orcid":false,"given":"Amritendu","family":"Dhar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7956-1470","authenticated-orcid":false,"given":"Vijay","family":"Natarajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2533-3699","authenticated-orcid":false,"given":"Abhishek","family":"Rathod","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,24]]},"reference":[{"key":"680_CR1","unstructured":"(2024) OFF format. http:\/\/www.geomview.org\/docs\/html\/OFF.html. Accessed 14 May 2024"},{"key":"680_CR2","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-642-04128-0_28","volume-title":"Algorithms\u2014ESA 2009","author":"E Amaldi","year":"2009","unstructured":"Amaldi, E., Iuliano, C., Jurkiewicz, T., et al.: Breaking the $${O}(m^2n)$$ barrier for minimum cycle bases. In: Fiat, A., Sanders, P. (eds.) Algorithms\u2014ESA 2009, pp. 301\u2013312. Springer, Berlin (2009)"},{"key":"680_CR3","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jsc.2016.03.008","volume":"78","author":"U Bauer","year":"2017","unstructured":"Bauer, U., Kerber, M., Reininghaus, J., et al.: PHAT\u2014persistent homology algorithms toolbox. J. Symb. Comput. 78, 76\u201390 (2017). https:\/\/doi.org\/10.1016\/j.jsc.2016.03.008","journal-title":"J. Symb. Comput."},{"key":"680_CR4","unstructured":"Bauer, U., Kerber, M., Reininghaus, J.: Persistent homology algorithm toolbox. https:\/\/github.com\/blazs\/phat. Accessed 14 May 2024 (2024)"},{"key":"680_CR5","unstructured":"Boost (2023) Boost library. https:\/\/boost.org. Accessed 18 April 2023"},{"issue":"2","key":"680_CR6","first-page":"58","volume":"8","author":"G Borradaile","year":"2017","unstructured":"Borradaile, G., Chambers, E.W., Fox, K., et al.: Minimum cycle and homology bases of surface-embedded graphs. JoCG 8(2), 58\u201379 (2017)","journal-title":"JoCG"},{"key":"680_CR7","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/978-3-642-31155-0_17","volume-title":"Algorithm Theory\u2014SWAT 2012","author":"O Busaryev","year":"2012","unstructured":"Busaryev, O., Cabello, S., Chen, C., et al.: Annotating simplices with a homology basis and its applications. In: Fomin, F.V., Kaski, P. (eds.) Algorithm Theory\u2014SWAT 2012, pp. 189\u2013200. Springer, Berlin (2012)"},{"issue":"2","key":"680_CR8","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.comgeo.2009.06.004","volume":"43","author":"C Chen","year":"2010","unstructured":"Chen, C., Freedman, D.: Measuring and computing natural generators for homology groups. Comput. Geom. Theory Appl. 43(2), 169\u2013181 (2010). https:\/\/doi.org\/10.1016\/j.comgeo.2009.06.004","journal-title":"Comput. Geom. Theory Appl."},{"issue":"3","key":"680_CR9","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s00454-010-9322-8","volume":"45","author":"C Chen","year":"2011","unstructured":"Chen, C., Freedman, D.: Hardness results for homology localization. Discret. Comput. Geom. 45(3), 425\u2013448 (2011). https:\/\/doi.org\/10.1007\/s00454-010-9322-8","journal-title":"Discret. Comput. Geom."},{"issue":"5","key":"680_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2528404","volume":"60","author":"HY Cheung","year":"2013","unstructured":"Cheung, H.Y., Kwok, T.C., Lau, L.C.: Fast matrix rank algorithms and applications. J. ACM 60(5), 1\u201325 (2013). https:\/\/doi.org\/10.1145\/2528404","journal-title":"J. ACM"},{"key":"680_CR11","unstructured":"de\u00a0Pina, J.C.: Applications of shortest path methods. PhD thesis, Universiteit van Amsterdam (1995)"},{"key":"680_CR12","doi-asserted-by":"publisher","unstructured":"Deem, M.: Michael Deem\u2019s PCOD and PCOD2 databases of zeolitic structures. https:\/\/doi.org\/10.5281\/zenodo.4030232 (2020)","DOI":"10.5281\/zenodo.4030232"},{"key":"680_CR13","doi-asserted-by":"publisher","unstructured":"Dey, T.K., Sun, J., Wang, Y.: Approximating loops in a shortest homology basis from point data. In: Proc. Twenty-Sixth Annual Symposium on Computational Geometry. Association for Computing Machinery, New York, NY, USA, SoCG \u201910, pp. 166\u2013175 (2010). https:\/\/doi.org\/10.1145\/1810959.1810989","DOI":"10.1145\/1810959.1810989"},{"key":"680_CR14","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-319-77404-6_28","volume-title":"LATIN 2018: Theoretical Informatics","author":"TK Dey","year":"2018","unstructured":"Dey, T.K., Li, T., Wang, Y.: Efficient algorithms for computing a minimal homology basis. In: Bender, M.A., Farach-Colton, M., Mosteiro, M.A. (eds.) LATIN 2018: Theoretical Informatics, pp. 376\u2013398. Springer, Cham (2018)"},{"key":"680_CR15","unstructured":"Dimitrios, M.: Parallel minimum cycle basis library. https:\/\/github.com\/d-michail\/parmcb. Accessed 14 May 2024 (2024)"},{"key":"680_CR16","doi-asserted-by":"publisher","unstructured":"Dumas, J.G., Pernet, C., Sultan, Z.: Simultaneous computation of the row and column rank profiles. In: Proc. 38th International Symposium on Symbolic and Algebraic Computation. ACM, New York, NY, USA, ISSAC \u201913, pp. 181\u2013188 (2013). https:\/\/doi.org\/10.1145\/2465506.2465517","DOI":"10.1145\/2465506.2465517"},{"key":"680_CR17","unstructured":"Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: Proc. Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, SODA \u201905, pp. 1038\u20131046 (2005)"},{"key":"680_CR18","volume-title":"Algebraic Topology","author":"A Hatcher","year":"2002","unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)"},{"issue":"2","key":"680_CR19","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1137\/0216026","volume":"16","author":"JD Horton","year":"1987","unstructured":"Horton, J.D.: A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput. 16(2), 358\u2013366 (1987). https:\/\/doi.org\/10.1137\/0216026","journal-title":"SIAM J. Comput."},{"key":"680_CR20","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.jsc.2013.04.004","volume":"56","author":"CP Jeannerod","year":"2013","unstructured":"Jeannerod, C.P., Pernet, C., Storjohann, A.: Rank-profile revealing gaussian elimination and the cup matrix decomposition. J. Symb. Comput. 56, 46\u201368 (2013). https:\/\/doi.org\/10.1016\/j.jsc.2013.04.004","journal-title":"J. Symb. Comput."},{"key":"680_CR21","doi-asserted-by":"publisher","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., Mehlhorn, K., Michail, D., et al.: A faster algorithm for minimum cycle basis of graphs. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., et al. (eds.) Automata, Languages and Programming, pp. 846\u2013857. Springer, Berlin (2004)"},{"issue":"4","key":"680_CR22","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.cosrev.2009.08.001","volume":"3","author":"T Kavitha","year":"2009","unstructured":"Kavitha, T., Liebchen, C., Mehlhorn, K., et al.: Cycle bases in graphs characterization, algorithms, complexity, and applications. Comput. Sci. Rev. 3(4), 199\u2013243 (2009). https:\/\/doi.org\/10.1016\/j.cosrev.2009.08.001","journal-title":"Comput. Sci. Rev."},{"issue":"4","key":"680_CR23","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00453-009-9313-4","volume":"59","author":"T Kavitha","year":"2011","unstructured":"Kavitha, T., Mehlhorn, K., Michail, D.: New approximation algorithms for minimum cycle bases of graphs. Algorithmica 59(4), 471\u2013488 (2011). https:\/\/doi.org\/10.1007\/s00453-009-9313-4","journal-title":"Algorithmica"},{"issue":"2","key":"680_CR24","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1021\/ci200386x","volume":"52","author":"RL Martin","year":"2012","unstructured":"Martin, R.L., Smit, B., Haranczyk, M.: Addressing challenges of identifying geometrically diverse sets of crystalline porous materials. J. Chem. Inf. Model. 52(2), 308\u2013318 (2012). https:\/\/doi.org\/10.1021\/ci200386x","journal-title":"J. Chem. Inf. Model."},{"issue":"1","key":"680_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1644015.1644023","volume":"6","author":"K Mehlhorn","year":"2009","unstructured":"Mehlhorn, K., Michail, D.: Minimum cycle bases: faster and simpler. ACM Trans. Algorithms 6(1), 1\u201313 (2009). https:\/\/doi.org\/10.1145\/1644015.1644023","journal-title":"ACM Trans. Algorithms"},{"key":"680_CR26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"680_CR27","unstructured":"Oleksiy, B., Tamal, D.K., Jian, S., et\u00a0al.: Shortloop software for computing loops in a shortest homology basis (2024). https:\/\/web.cse.ohio-state.edu\/~dey.8\/shortloop.html. Accessed 14 May 2024"},{"key":"680_CR28","unstructured":"Rathod, A.: Fast algorithms for minimum cycle basis and minimum homology basis. In: Proc. International Symposium on Com putational Geometry (SoCG 2020), pp. 1\u201311 (2020)"},{"key":"680_CR29","doi-asserted-by":"publisher","unstructured":"Storjohann, A., Yang, S.: Linear independence oracles and applications to rectangular and low rank linear systems. In: Proc. 39th International Symposium on Symbolic and Algebraic Computation. ACM, New York, NY, USA, ISSAC \u201914, pp. 381\u2013388 (2014). https:\/\/doi.org\/10.1145\/2608628.2608673","DOI":"10.1145\/2608628.2608673"},{"key":"680_CR30","doi-asserted-by":"publisher","unstructured":"Storjohann, A., Yang, S.: A relaxed algorithm for online matrix inversion. In: Proc. 2015 ACM on International Symposium on Symbolic and Algebraic Computation. ACM, New York, NY, USA, ISSAC \u201915, pp. 339\u2013346 (2015). https:\/\/doi.org\/10.1145\/2755996.2756672","DOI":"10.1145\/2755996.2756672"},{"key":"680_CR31","unstructured":"Visionair (2024) http:\/\/visionair.ge.imati.cnr.it\/. Accessed 14 May 2024"},{"issue":"1","key":"680_CR32","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","volume":"32","author":"D Wiedemann","year":"1986","unstructured":"Wiedemann, D.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory 32(1), 54\u201362 (1986). https:\/\/doi.org\/10.1109\/TIT.1986.1057137","journal-title":"IEEE Trans. Inf. Theory"},{"key":"680_CR33","unstructured":"Yang, S.: Algorithms for fast linear system solving and rank profile computation. Master\u2019s thesis, University of Waterloo (2014)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00680-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00680-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00680-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:14:16Z","timestamp":1750281256000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00680-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,24]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["680"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00680-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,7,24]]},"assertion":[{"value":"13 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}