{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:14:53Z","timestamp":1781259293747,"version":"3.54.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,6,3]],"date-time":"2009-06-03T00:00:00Z","timestamp":1243987200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,4]]},"DOI":"10.1007\/s00453-009-9328-x","type":"journal-article","created":{"date-parts":[[2009,6,2]],"date-time":"2009-06-02T14:01:30Z","timestamp":1243951290000},"page":"621-633","source":"Crossref","is-referenced-by-count":13,"title":["All-Pairs Bottleneck Paths in Vertex Weighted Graphs"],"prefix":"10.1007","volume":"59","author":[{"given":"Asaf","family":"Shapira","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,6,3]]},"reference":[{"key":"9328_CR1","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1007\/BF01940874","volume":"16","author":"N. Alon","year":"1996","unstructured":"Alon, N., Naor, M.: Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica 16, 434\u2013449 (1996)","journal-title":"Algorithmica"},{"issue":"2","key":"9328_CR2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.jalgor.2005.08.001","volume":"57","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Farach-Colton, M., Pemmasani, G., Skiena, S., Sumazin, P.: Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms 57(2), 75\u201394 (2005)","journal-title":"J. Algorithms"},{"key":"9328_CR3","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press, Cambridge (2001)","edition":"2"},{"key":"9328_CR4","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1006\/jcom.1997.0438","volume":"13","author":"D. Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Rectangular matrix multiplication revisited. J. Complex. 13, 42\u201349 (1997)","journal-title":"J. Complex."},{"key":"9328_CR5","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"9328_CR6","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.tcs.2007.02.053","volume":"380","author":"A. Czumaj","year":"2007","unstructured":"Czumaj, A., Kowaluk, M., Lingas, A.: Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theor. Comput. Sci. 380, 37\u201346 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9328_CR7","unstructured":"Czumaj, A., Lingas, A.: Finding a heaviest triangle is not harder than matrix multiplication. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 986\u2013994 (2007)"},{"key":"9328_CR8","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Fast algorithms for (Max,Min)-matrix multiplication and bottleneck shortest paths In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 384\u2013391 (2009)","DOI":"10.1137\/1.9781611973068.43"},{"key":"9328_CR9","doi-asserted-by":"crossref","unstructured":"Fischer, M.J., Meyer, A.R.: Boolean matrix multiplication and transitive closure. In: Proceedings of the 12th Symposium on Switching and Automata Theory, East Lansing, MI, pp. 129\u2013131 (1971)","DOI":"10.1109\/SWAT.1971.4"},{"key":"9328_CR10","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 596\u2013615 (1987)","journal-title":"J. ACM"},{"issue":"5","key":"9328_CR11","first-page":"1252","volume":"11","author":"M.E. Furman","year":"1970","unstructured":"Furman, M.E.: Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph. Dokl. Akad. Nauk SSSR 11(5), 1252 (1970)","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"2","key":"9328_CR12","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1006\/jcom.1993.1014","volume":"9","author":"Z. Galil","year":"1993","unstructured":"Galil, Z., Margalit, O.: Witnesses for Boolean matrix multiplication and for transitive closure. J. Complex. 9(2), 201\u2013221 (1993)","journal-title":"J. Complex."},{"issue":"3","key":"9328_CR13","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/0196-6774(88)90031-4","volume":"9","author":"H.N. Gabow","year":"1988","unstructured":"Gabow, H.N., Tarjan, R.E.: Algorithms for two bottleneck optimization problems. J. Algorithms 9(3), 411\u2013417 (1988)","journal-title":"J. Algorithms"},{"key":"9328_CR14","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1006\/jcom.1998.0476","volume":"14","author":"X. Huang","year":"1998","unstructured":"Huang, X., Pan, V.Y.: Fast rectangular matrix multiplications and applications. J. Complex. 14, 257\u2013299 (1998)","journal-title":"J. Complex."},{"key":"9328_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/11523468_20","volume-title":"Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP)","author":"M. Kowaluk","year":"2005","unstructured":"Kowaluk, M., Lingas, A.: LCA queries in directed acyclic graphs. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 3580, pp. 241\u2013248. Springer, Berlin (2005)"},{"key":"9328_CR16","unstructured":"Munro, I.: Efficient determination of the strongly connected components and the transitive closure of a graph. Unpublished manuscript, Univ. of Toronto, Toronto, Canada (1971)"},{"key":"9328_CR17","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"R.C. Prim","year":"1957","unstructured":"Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 1389\u20131401 (1957)","journal-title":"Bell Syst. Tech. J."},{"issue":"3","key":"9328_CR18","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 51(3), 400\u2013403 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9328_CR19","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R.: Finding a maximum weight triangle in n 3\u2212\u03b4 time, with applications. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp. 225\u2013231 (2006)","DOI":"10.1145\/1132516.1132550"},{"key":"9328_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/11786986_24","volume-title":"Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP)","author":"V. Vassilevska","year":"2006","unstructured":"Vassilevska, V., Williams, R., Yuster, R.: Finding the smallest H-subgraph in real weighted graphs and related problems. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 4051, pp. 262\u2013273. Springer, Berlin (2006)"},{"key":"9328_CR21","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R., Yuster, R.: All-pairs bottleneck paths in truly sub-cubic time. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 585\u2013589 (2007)","DOI":"10.1145\/1250790.1250876"},{"key":"9328_CR22","doi-asserted-by":"crossref","unstructured":"Zwick, U.: All pairs lightest shortest paths. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 61\u201369 (1999)","DOI":"10.1145\/301250.301271"},{"key":"9328_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/3-540-44676-1_3","volume-title":"Proceedings of the 9th Annual European Symposium on Algorithms (ESA)","author":"U. Zwick","year":"2001","unstructured":"Zwick, U.: Exact approximate distances in graphs\u2014a survey. In: Proceedings of the 9th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 2161, pp. 33\u201348. Springer, Berlin (2001)"},{"key":"9328_CR24","doi-asserted-by":"crossref","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, 289\u2013317 (2002)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9328-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9328-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9328-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:04Z","timestamp":1559123104000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9328-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,3]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["9328"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9328-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6,3]]}}}