{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T10:40:29Z","timestamp":1774435229612,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1995,5,1]],"date-time":"1995-05-01T00:00:00Z","timestamp":799286400000},"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":[[1995,5]]},"DOI":"10.1007\/bf01190847","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T11:21:25Z","timestamp":1108725685000},"page":"426-441","source":"Crossref","is-referenced-by-count":26,"title":["All-pairs shortest paths and the essential subgraph"],"prefix":"10.1007","volume":"13","author":[{"given":"C. C.","family":"McGeoch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/77600.77615","volume":"37","author":"R. K. Ahuja","year":"1990","unstructured":"R. K. Ahuja, K. Mehlhorn, J. B. Orlin, and R. E. Tarjan. Faster algorithms for the shortest path problem.J. Assoc. Comput. Mach.,37 (1990), 213?223.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR2","unstructured":"N. Alon, Z. Galil, and O. Margalit. On the exponent of the all pairs shortest path problem.Proc. 32nd FOCS, 1991, pp. 569?575."},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"G. Ausiello, G. F. Italiano, A. M. Spaccamela, and U. Nanni. Incremental algorithms for minimal length paths.Proc. First SODA, 1990 pp. 12?21.","DOI":"10.1016\/0196-6774(91)90036-X"},{"issue":"3","key":"CR4","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1145\/355900.355907","volume":"6","author":"J. L. Bentley","year":"1980","unstructured":"J. L. Bentley and J. B. Saxe. Generating sorted lists of random numbers.ACM Trans. Math. Software,6(3) (1980), 359?364.","journal-title":"ACM Trans. Math. Software"},{"issue":"3","key":"CR5","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1137\/0212039","volume":"12","author":"P. A. Bloniarz","year":"1983","unstructured":"P. A. Bloniarz. A shortest-path algorithm with expected time o(n2 logn log* n).SIAM J. Comput.,12(3) (1983), 588?600.","journal-title":"SIAM J. Comput."},{"key":"CR6","volume-title":"Random Graphs","author":"B. Bollob\u00e1s","year":"1985","unstructured":"B. Bollob\u00e1s.Random Graphs. Academic Press, New York, 1985."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra. A note on two problems in connexion with graphs.Numer. Math.,1 (1959), 269?271.","journal-title":"Numer. Math."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P. Erd\u00f6s","year":"1959","unstructured":"P. Erd\u00f6s and A. R\u00e9nyi. On random graphs, I.Publ. Math. Debrecen,6 (1959), 290?297.","journal-title":"Publ. Math. Debrecen"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R. W. Floyd","year":"1962","unstructured":"R. W. Floyd. Algorithm 97: Shortest path.Comm. ACM,5 (1962), 345.","journal-title":"Comm. ACM"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"M. L. Fredman","year":"1976","unstructured":"M. L. Fredman. New bounds on the complexity of the shortest path problem.SIAM J. Comput.,5 (1976), 83?89.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"CR11","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms.J. Assoc. Comput. Mach.,34(3) (1987), 596?615.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"M. L. Fredman and D. E. Willard. Trans-dichotomous algorithms for minimum spanning trees and shortest paths.Proc. 31st FOCS, October 1990, pp. 719?725.","DOI":"10.1109\/FSCS.1990.89594"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0166-218X(85)90058-7","volume":"10","author":"A. M. Frieze","year":"1985","unstructured":"A. M. Frieze. On the value of a random minimum spanning tree problem.Discrete Appl. Math.,10 (1985), 47?56.","journal-title":"Discrete Appl. Math."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"A. M. Frieze","year":"1985","unstructured":"A. M. Frieze and G. R. Grimmet. The shortest-path problem for graphs with random arc-lengths.Discrete Appl. Math.,10 (1985), 57?77.","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"CR15","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1287\/moor.10.4.557","volume":"10","author":"R. Hassin","year":"1985","unstructured":"R. Hassin and E. Zemel. On the shortest paths in graphs with random weights.Math. Oper. Res.,10(4) (1985), 557?564.","journal-title":"Math. Oper. Res."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"D. B. Johnson","year":"1977","unstructured":"D. B. Johnson. Efficient algorithms for shortest paths in sparse networks.J. Assoc. Comput. Mach.,24 (1977), 1?13.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"6","key":"CR17","doi-asserted-by":"crossref","first-page":"1199","DOI":"10.1137\/0222071","volume":"22","author":"D. R. Karger","year":"1993","unstructured":"D. R. Karger, D. Koller, and S. J. Phillips. Finding the hidden path: time bounds for all-pairs shortest paths.SIAM J. Comput.,22(6) (1993), 1199?1217.","journal-title":"SIAM J. Comput."},{"issue":"6","key":"CR18","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1137\/0216065","volume":"16","author":"A. Moffat","year":"1987","unstructured":"A. Moffat and T. Takoaka. An all pairs shortest path algorithm with expected time o(n2 logn).SIAM J. Comput.,16(6) (1987), 1023?1031.","journal-title":"SIAM J. Comput."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0196-6774(92)90017-7","volume":"13","author":"K. V. S. Ramaro","year":"1992","unstructured":"K. V. S. Ramaro and S. Venkatesan. On finding and updating shortest paths distributively.J. Algorithms,13 (1992), 235?257.","journal-title":"J. Algorithms"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/0095-8956(71)90053-0","volume":"10","author":"P. Robert","year":"1971","unstructured":"P. Robert. An algorithm for finding the essential sets of arcs of certain graphs.J. Combin. Theory,10 (1971), 288?298.","journal-title":"J. Combin. Theory"},{"key":"CR21","volume-title":"Algorithms","author":"R. Sedgewich","year":"1988","unstructured":"R. Sedgewich.Algorithms. Addison-Wesley, Reading, MA, 1988."},{"issue":"1","key":"CR22","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0202004","volume":"2","author":"P. M. Spira","year":"1973","unstructured":"P. M. Spira. A new algorithm for finding all shortest paths in a graph of positive arcs in average time 0(n2 logn).SIAM J. Comput.,2(1) (1973) 28?32.","journal-title":"SIAM J. Comput."},{"key":"CR23","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan.Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983."},{"issue":"3","key":"CR24","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1137\/0209041","volume":"9","author":"B. W. Weide","year":"1980","unstructured":"B. W. Weide. Random graphs and graph optimization problems.SIAM J. Comput.,9(3) (1980), 552?557.","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190847.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01190847\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01190847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T06:39:57Z","timestamp":1683009597000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01190847"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,5]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1995,5]]}},"alternative-id":["BF01190847"],"URL":"https:\/\/doi.org\/10.1007\/bf01190847","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,5]]}}}