{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:44:04Z","timestamp":1742921044203,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":19,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_11","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:37:51Z","timestamp":1214505471000},"page":"28-31","source":"Crossref","is-referenced-by-count":0,"title":["All Pairs Shortest Paths in Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1_11","volume-title":"The design and analysis of computer algorithms","author":"A.V. Aho","year":"1975","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Addison\u2010Wesley, Reading (1975)"},{"doi-asserted-by":"crossref","unstructured":"Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant shortest-path queries in road networks. In: Proc. 9th Workshop on Algorithm Engineering and Experiments (ALENEX), 2007","key":"11_CR2_11","DOI":"10.1137\/1.9781611972870.5"},{"doi-asserted-by":"crossref","unstructured":"Chan, T.: More algorithms for all-pairs shortest paths in weighted graphs. In: Proc.\u00a039th ACM Symposium on Theory of Computing (STOC), 2007, pp.\u00a0590\u2013598","key":"11_CR3_11","DOI":"10.1145\/1250790.1250877"},{"key":"11_CR4_11","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.: 9th DIMACS Implementation challenge \u2013 shortest paths. http:\/\/www.dis.uniroma1.it\/~challenge9\/ (2006)","key":"11_CR5_11"},{"issue":"1","key":"11_CR6_11","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"M.L. Fredman","year":"1976","unstructured":"Fredman, M.L.: New bounds on the complexity of the shortest path problem. SIAM J. Comput. 5(1), 83\u201389 (1976)","journal-title":"SIAM J. Comput."},{"key":"11_CR7_11","volume-title":"Computers and Intractability: a guide to NP\u2010Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: a\u00a0guide to NP\u2010Completeness. Freeman, San Francisco (1979)"},{"unstructured":"Goldberg, A.V.: AVG Lab. http:\/\/www.avglab.com\/andrew\/","key":"11_CR8_11"},{"key":"11_CR9_11","first-page":"502","volume-title":"Proc. 12th Int'l Symp. on Algorithms and Computation (ISAAC). LNCS, vol. 2223","author":"A.V. Goldberg","year":"2001","unstructured":"Goldberg, A.V.: Shortest path algorithms: Engineering aspects. In: Proc.\u00a012th Int'l Symp. on Algorithms and Computation (ISAAC). LNCS, vol. 2223, pp.\u00a0502\u2013513. Springer, Berlin (2001)"},{"doi-asserted-by":"crossref","unstructured":"Goldberg, A.V., Kaplan, H., Werneck, R.: Reach for A*: efficient point-to-point shortest path algorithms. In: Proc.\u00a08th Workshop on Algorithm Engineering and Experiments (ALENEX), 2006","key":"11_CR10_11","DOI":"10.1137\/1.9781611972863.13"},{"doi-asserted-by":"crossref","unstructured":"Knopp, S., Sanders, P., Schultes, D., Schulz, F., Wagner, D.: Computing many-to-many shortest paths using highway hierarchies. In: Proc.\u00a09th Workshop on Algorithm Engineering and Experiments (ALENEX), 2007","key":"11_CR11_11","DOI":"10.1137\/1.9781611972870.4"},{"doi-asserted-by":"crossref","unstructured":"Pettie, S.: On the comparison\u2010addition complexity of all-pairs shortest paths. In: Proc.\u00a013th Int'l Symp. on Algorithms and Computation (ISAAC), 2002, pp.\u00a032\u201343","key":"11_CR12_11","DOI":"10.1007\/3-540-36136-7_4"},{"issue":"1","key":"11_CR13_11","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(03)00402-X","volume":"312","author":"S. Pettie","year":"2004","unstructured":"Pettie, S.: A\u00a0new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci. 312(1), 47\u201374 (2004)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Pettie, S., Ramachandran, V.: Minimizing randomness in minimum spanning tree, parallel connectivity and set maxima algorithms. In: Proc.\u00a013th\u00a0ACM-SIAM Symp. on Discrete Algorithms (SODA), 2002, pp.\u00a0713\u2013722","key":"11_CR14_11"},{"issue":"6","key":"11_CR15_11","doi-asserted-by":"publisher","first-page":"1398","DOI":"10.1137\/S0097539702419650","volume":"34","author":"S. Pettie","year":"2005","unstructured":"Pettie, S., Ramachandran, V.: A\u00a0shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput. 34(6), 1398\u20131431 (2005)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Pettie, S., Ramachandran, V., Sridhar, S.: Experimental evaluation of a\u00a0new shortest path algorithm. In: Proc.\u00a04th Workshop on Algorithm Engineering and Experiments (ALENEX), 2002, pp.\u00a0126\u2013142","key":"11_CR16_11","DOI":"10.1007\/3-540-45643-0_10"},{"issue":"3","key":"11_CR17_11","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single\u2010source shortest paths with positive integer weights in linear time. J. ACM 46(3), 362\u2013394 (1999)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Venkataraman, G., Sahni, S., Mukhopadhyaya, S.: A\u00a0blocked all-pairs shortest paths algorithm. J. Exp. Algorithms 8 (2003)","key":"11_CR18_11","DOI":"10.1145\/996546.996553"},{"doi-asserted-by":"crossref","unstructured":"Zwick, U.: Exact and approximate distances in graphs \u2013 a\u00a0survey. In: Proc.\u00a09th European Symposium on Algorithms (ESA), 2001, pp.\u00a033\u201348. See updated version at http:\/\/www.cs.tau.ac.il\/~zwick\/","key":"11_CR19_11","DOI":"10.1007\/3-540-44676-1_3"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T02:01:22Z","timestamp":1662170482000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_11"}},"subtitle":["2004; Pettie"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_11","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}