{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T01:52:11Z","timestamp":1774317131579,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,11,21]],"date-time":"2018-11-21T00:00:00Z","timestamp":1542758400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2014\/13\/B\/ST6\/00770"],"award-info":[{"award-number":["2014\/13\/B\/ST6\/00770"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2016\/21\/N\/ST6\/001468"],"award-info":[{"award-number":["2016\/21\/N\/ST6\/001468"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s00224-018-9894-x","type":"journal-article","created":{"date-parts":[[2018,11,20]],"date-time":"2018-11-20T23:27:28Z","timestamp":1542756448000},"page":"1049-1067","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Improved Distance Queries and Cycle Counting by Frobenius Normal Form"],"prefix":"10.1007","volume":"63","author":[{"given":"Piotr","family":"Sankowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9746-5733","authenticated-orcid":false,"given":"Karol","family":"W\u0119grzycki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,11,21]]},"reference":[{"key":"9894_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Grandoni, F., Williams, V.V.: Subcubic equivalences between graph centrality problems, APSP and diameter. In: Indyk, P. (ed.) Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 1681\u20131697. SIAM, San Diego (2015). ISBN 978-1-61197-374-7. \n                    https:\/\/doi.org\/10.1137\/1.9781611973730.112","DOI":"10.1137\/1.9781611973730.112"},{"key":"9894_CR2","doi-asserted-by":"publisher","unstructured":"Abboud, A., Williams, VV, Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: Krauthgamer, R. (ed.) Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 377\u2013391. SIAM, Arlington (2016). ISBN 978-1-61197-433-1. \n                    https:\/\/doi.org\/10.1137\/1.9781611974331.ch28","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"9894_CR3","doi-asserted-by":"publisher","unstructured":"Agarwal, U, Ramachandran, V: Fine-grained complexity for sparse graphs. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pp. 239\u2013252. ACM, Los Angeles (2018). \n                    https:\/\/doi.org\/10.1145\/3188745.3188888","DOI":"10.1145\/3188745.3188888"},{"issue":"4","key":"9894_CR4","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42 (4), 844\u2013856 (1995). \n                    https:\/\/doi.org\/10.1145\/210332.210337","journal-title":"J. ACM"},{"issue":"3","key":"9894_CR5","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R, Zwick, U: Finding and counting given length cycles. Algorithmica 17(3), 209\u2013223 (1997). \n                    https:\/\/doi.org\/10.1007\/BF02523189","journal-title":"Algorithmica"},{"key":"9894_CR6","doi-asserted-by":"publisher","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. In: Johnson, D.S., Feige, U. (eds.) Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 590\u2013598. ACM, San Diego (2007). ISBN 978-1-59593-631-8. \n                    https:\/\/doi.org\/10.1145\/1250790.1250877","DOI":"10.1145\/1250790.1250877"},{"issue":"3","key":"9894_CR7","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1137\/S0895480191217776","volume":"7","author":"FRK Chung","year":"1994","unstructured":"Chung, F.R.K., Faber, V., Manteuffel, T.A.: An upper bound on the diameter of a graph from eigenvalues associated with its laplacian. SIAM J. Discrete Math. 7(3), 443\u2013457 (1994). \n                    https:\/\/doi.org\/10.1137\/S0895480191217776","journal-title":"SIAM J. Discrete Math."},{"key":"9894_CR8","unstructured":"Chung, F.R.K.: Spectral graph theory, volume 92 American Mathematical Soc. (1997)"},{"issue":"4","key":"9894_CR9","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/2736283","volume":"62","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Gabow, H.N., Sankowski, P.: Algorithmic applications of baur-strassen\u2019s theorem: shortest cycles, diameter, and matchings. J. ACM 62(4), 28 (2015). \n                    https:\/\/doi.org\/10.1145\/2736283","journal-title":"J. ACM"},{"key":"9894_CR10","doi-asserted-by":"publisher","unstructured":"Eberly, W: Black box frobenius decompositions over small fields. In: [28], pp. 106\u2013113. ISBN 1-58113-218-2. \n                    https:\/\/doi.org\/10.1145\/345542.345596","DOI":"10.1145\/345542.345596"},{"issue":"6","key":"9894_CR11","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"RW Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: shortest path. Commun. ACM 5(6), 345 (1962). \n                    https:\/\/doi.org\/10.1145\/367766.368168","journal-title":"Commun. ACM"},{"key":"9894_CR12","doi-asserted-by":"crossref","unstructured":"Frandsen, GS, Sankowski, P: Dynamic normal forms and dynamic characteristic polynomial. In: International Colloquium on Automata, Languages, and Programming, pp. 434\u2013446. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-70575-8_36"},{"key":"9894_CR13","unstructured":"Gantmacher, F.R.: The theory of matrices, Vol. 1 Chelsea (1959)"},{"key":"9894_CR14","doi-asserted-by":"publisher","unstructured":"Giesbrecht, M., Jacobson, M.J. Jr, Storjohann, A.: Algorithms for large integer matrix problems. In: Boztas, S., Shparlinski, I.E. (eds.) 14th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-14. Proceedings, volume 2227 of Lecture Notes in Computer Science, pp. 297\u2013307. Springer, Melbourne (2001). ISBN 3-540-42911-5. \n                    https:\/\/doi.org\/10.1007\/3-540-45624-4_31","DOI":"10.1007\/3-540-45624-4_31"},{"key":"9894_CR15","volume-title":"Matrix computations","author":"GH Golub","year":"1996","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996). ISBN 978-0-8018-5414-9","edition":"3rd edn."},{"key":"9894_CR16","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 296\u2013303. ACM (2014)","DOI":"10.1145\/2608628.2608664"},{"issue":"11","key":"9894_CR17","doi-asserted-by":"publisher","first-page":"2921","DOI":"10.1016\/j.laa.2011.05.021","volume":"435","author":"A Lim","year":"2011","unstructured":"Lim, A., Dai, J.: On product of companion matrices. Linear Algebra Appl. 435(11), 2921\u20132935 (2011)","journal-title":"Linear Algebra Appl."},{"key":"9894_CR18","doi-asserted-by":"publisher","unstructured":"Mulders, T., Storjohann, A.: Rational solutions of singular linear systems. In: [28], pp. 242\u2013249. ISBN 1-58113-218-2. \n                    https:\/\/doi.org\/10.1145\/345542.345644","DOI":"10.1145\/345542.345644"},{"issue":"2","key":"9894_CR19","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1006\/jagm.1995.0807","volume":"22","author":"JH Reif","year":"1997","unstructured":"Reif, J.H., Tate, S.R.: On dynamic algorithms for algebraic problems. J. Algorithms 22(2), 347\u2013371 (1997). \n                    https:\/\/doi.org\/10.1006\/jagm.1995.0807","journal-title":"J. Algorithms"},{"issue":"4","key":"9894_CR20","doi-asserted-by":"publisher","first-page":"45:1","DOI":"10.1145\/2000807.2000813","volume":"7","author":"L Roditty","year":"2011","unstructured":"Roditty, L., Shapira, A.: All-pairs shortest paths with a sublinear additive error. ACM Trans. Algorithms 7(4), 45:1\u201345:12 (2011). ISSN 1549-6325. \n                    https:\/\/doi.org\/10.1145\/2000807.2000813","journal-title":"ACM Trans. Algorithms"},{"key":"9894_CR21","doi-asserted-by":"publisher","unstructured":"Roditty, L., Williams, V.V.: Minimum weight cycles and triangles: equivalences and algorithms. In: Ostrovsky, R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 180\u2013189. IEEE Computer Society, Palm Springs (2011). \n                    https:\/\/doi.org\/10.1109\/FOCS.2011.27","DOI":"10.1109\/FOCS.2011.27"},{"key":"9894_CR22","doi-asserted-by":"publisher","unstructured":"Sankowski, P., Wegrzycki, K.: Improved distance queries and cycle counting by frobenius normal form. In: Vollmer, H., Vall\u00e9e, B. (eds.) 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, vol. 66 of LIPIcs, pp. 56:1\u201356:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Hannover (2017). ISBN 978-3-95977-028-6. \n                    https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2017.56","DOI":"10.4230\/LIPIcs.STACS.2017.56"},{"issue":"4","key":"9894_CR23","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717 (1980). ISSN 0004-5411. \n                    https:\/\/doi.org\/10.1145\/322217.322225","journal-title":"J. ACM"},{"key":"9894_CR24","doi-asserted-by":"publisher","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem. In: Rao Kosaraju, S., Fellows, M., Wigderson, A., Ellis, J.A. (eds.) Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, pp. 745\u2013749. ACM, Victoria (1992). ISBN 0-89791-511-9. \n                    https:\/\/doi.org\/10.1145\/129712.129784","DOI":"10.1145\/129712.129784"},{"key":"9894_CR25","doi-asserted-by":"publisher","unstructured":"Storjohann, A.: Deterministic computation of the frobenius form. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, pp. 368\u2013377. IEEE Computer Society, Las Vegas (2001). ISBN 0-7695-1390-5. \n                    https:\/\/doi.org\/10.1109\/SFCS.2001.959911","DOI":"10.1109\/SFCS.2001.959911"},{"key":"9894_CR26","unstructured":"Tang, Z., Duraiswami, R., Gumerov, N.A.: Fast algorithms to compute matrix-vector products for pascal matrices. Technical Reports from UMIACS UMIACS-TR-2004-08, 2004\/03\/25\/. \n                    http:\/\/drum.lib.umd.edu\/handle\/1903\/1338\n                    \n                   (2004)"},{"issue":"3","key":"9894_CR27","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. J. ACM 46(3), 362\u2013394 (1999). \n                    https:\/\/doi.org\/10.1145\/316542.316548","journal-title":"J. ACM"},{"key":"9894_CR28","volume-title":"Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation, ISSAC 2000","year":"2000","unstructured":"Traverso, C. (ed.): Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation, ISSAC 2000. ACM, St. Andrews (2000). ISBN 1-58113-218-2. \n                    http:\/\/dl.acm.org\/citation.cfm?id=345542"},{"issue":"1","key":"9894_CR29","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S Warshall","year":"1962","unstructured":"Warshall, S.: A theorem on boolean matrices. J. ACM 9(1), 11\u201312 (1962). \n                    https:\/\/doi.org\/10.1145\/321105.321107","journal-title":"J. ACM"},{"key":"9894_CR30","doi-asserted-by":"publisher","unstructured":"Williams, R.: Faster all-pairs shortest paths via circuit complexity. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC 2014, pp. 664\u2013673. ACM, New York (2014). ISBN 978-1-4503-2710-7. \n                    https:\/\/doi.org\/10.1145\/2591796.2591811","DOI":"10.1145\/2591796.2591811"},{"issue":"21-22","key":"9894_CR31","doi-asserted-by":"publisher","first-page":"1057","DOI":"10.1016\/j.ipl.2011.07.019","volume":"111","author":"R Yuster","year":"2011","unstructured":"Yuster, R.: A shortest cycle for each vertex of a graph. Inf. Process. Lett. 111 (21-22), 1057\u20131061 (2011). \n                    https:\/\/doi.org\/10.1016\/j.ipl.2011.07.019","journal-title":"Inf. Process. Lett."},{"key":"9894_CR32","doi-asserted-by":"publisher","unstructured":"Yuster, R., Zwick, U.: Finding even cycles even faster. In: Abiteboul, S., Shamir, E. (eds.) 21st International Colloquium, Automata, Languages and Programming, ICALP94. Proceedings, volume 820 of Lecture Notes in Computer Science, pp. 532\u2013543. Springer, Jerusalem (1994). ISBN 3-540-58201-0. \n                    https:\/\/doi.org\/10.1007\/3-540-58201-0_96","DOI":"10.1007\/3-540-58201-0_96"},{"key":"9894_CR33","doi-asserted-by":"publisher","unstructured":"Yuster, R., Zwick, U.: Answering distance queries in directed graphs using fast matrix multiplication. In: Proceedings of 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, pp. 389\u2013396. IEEE Computer Society (2005). ISBN 0-7695-2468-0. \n                    https:\/\/doi.org\/10.1109\/SFCS.2005.20","DOI":"10.1109\/SFCS.2005.20"},{"key":"9894_CR34","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and algebraic computation, pp. 216\u2013226. Springer, Berlin (1979). ISBN 978-3-540-35128-3"},{"issue":"3","key":"9894_CR35","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/567112.567114","volume":"49","author":"U Zwick","year":"2002","unstructured":"Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. J. ACM 49(3), 289\u2013317 (2002). \n                    https:\/\/doi.org\/10.1145\/567112.567114","journal-title":"J. ACM"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9894-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9894-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9894-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,20]],"date-time":"2019-11-20T19:07:45Z","timestamp":1574276865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9894-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,21]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["9894"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9894-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,21]]},"assertion":[{"value":"21 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}