{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:42:34Z","timestamp":1742956954436,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":20,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_11","type":"book-chapter","created":{"date-parts":[[2016,4,21]],"date-time":"2016-04-21T20:03:52Z","timestamp":1461269032000},"page":"52-55","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"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","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"1_CR1195","volume-title":"The design and analysis of computer algorithms","author":"AV Aho","year":"1975","unstructured":"Aho AV, Hopcroft JE, Ullman JD (1975) The design and analysis of computer algorithms. Addison-Wesley, Reading"},{"key":"1_CR1196","doi-asserted-by":"crossref","unstructured":"Bast H, Funke S, Matijevic D, Sanders P, Schultes D (2007) In transit to constant shortest-path queries in road networks. In: Proceedings of the 9th workshop on algorithm engineering and experiments (ALENEX), San Francisco","DOI":"10.1137\/1.9781611972870.5"},{"key":"1_CR1197","doi-asserted-by":"crossref","unstructured":"Chan T (2007) More algorithms for all-pairs shortest paths in weighted graphs. In: Proceedings of the 39th ACM symposium on theory of computing (STOC), San Diego, pp\u00a0590\u2013598","DOI":"10.1145\/1250790.1250877"},{"key":"1_CR1198","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT, Cambridge"},{"key":"1_CR1199","unstructured":"Demetrescu C, Goldberg AV, Johnson D (2006) 9th DIMACS implementation challenge \u2013 shortest paths. http:\/\/www.dis.uniroma1.it\/~challenge9\/"},{"issue":"1","key":"1_CR1200","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"ML Fredman","year":"1976","unstructured":"Fredman ML (1976) New bounds on the complexity of the shortest path problem. SIAM J Comput 5(1):83\u201389","journal-title":"SIAM J Comput"},{"key":"1_CR1201","volume-title":"Computers and intractability: a guide to NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to NP-completeness. Freeman, San Francisco"},{"key":"1_CR1202","doi-asserted-by":"crossref","unstructured":"Goldberg AV (2001) Shortest path algorithms: engineering aspects. In: Proceedings of the 12th international symposium on algorithms and computation (ISAAC), Christchurch. LNCS, vol\u00a02223. Springer, Berlin, pp\u00a0502\u2013513","DOI":"10.1007\/3-540-45678-3_43"},{"key":"1_CR1203","doi-asserted-by":"crossref","unstructured":"Goldberg AV, Kaplan H, Werneck R (2006) Reach for A*: efficient point-to-point shortest path algorithms. In: Proceedings of the 8th workshop on algorithm engineering and experiments (ALENEX), Miami","DOI":"10.1137\/1.9781611972863.13"},{"key":"1_CR1204","doi-asserted-by":"crossref","unstructured":"Knopp S, Sanders P, Schultes D, Schulz F, Wagner D (2007) Computing many-to-many shortest paths using highway hierarchies. In: Proceedings of the 9th workshop on algorithm engineering and experiments (ALENEX), New Orleans","DOI":"10.1137\/1.9781611972870.4"},{"key":"1_CR1205","doi-asserted-by":"crossref","unstructured":"Pettie S (2002) On the comparison-addition complexity of all-pairs shortest paths. In: Proceedings of the 13th international symposium on algorithms and computation (ISAAC), Vancouver, pp\u00a032\u201343","DOI":"10.1007\/3-540-36136-7_4"},{"issue":"1","key":"1_CR1206","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 (2004) A new approach to all-pairs shortest paths on real-weighted graphs. Theor Comput Sci 312(1):47\u201374","journal-title":"Theor Comput Sci"},{"key":"1_CR1207","unstructured":"Pettie S, Ramachandran V (2002) Minimizing randomness in minimum spanning tree, parallel connectivity and set maxima algorithms. In: Proceedings of the 13th ACM-SIAM symposium on discrete algorithms (SODA), San Francisco, pp\u00a0713\u2013722"},{"issue":"6","key":"1_CR1208","doi-asserted-by":"publisher","first-page":"1398","DOI":"10.1137\/S0097539702419650","volume":"34","author":"S Pettie","year":"2005","unstructured":"Pettie S, Ramachandran V (2005) A shortest path algorithm for real-weighted undirected graphs. SIAM J Comput 34(6):1398\u20131431","journal-title":"SIAM J Comput"},{"key":"1_CR1209","doi-asserted-by":"crossref","unstructured":"Pettie S, Ramachandran V, Sridhar S (2002) Experimental evaluation of a new shortest path algorithm. In: Proceedings of the 4th workshop on algorithm engineering and experiments (ALENEX), San Francisco, pp\u00a0126\u2013142","DOI":"10.1007\/3-540-45643-0_10"},{"issue":"3","key":"1_CR1210","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M Thorup","year":"1999","unstructured":"Thorup M (1999) Undirected single-source shortest paths with positive integer weights in linear time. J ACM 46(3):362\u2013394","journal-title":"J ACM"},{"key":"1_CR1211","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams V, Williams R (2010) Subcubic equivalences between path, matrix, and triangle problems. In Proceedings of the 51st IEEE symposium on foundations of computer science (FOCS), Los Alamitos, pp\u00a0645\u2013654","DOI":"10.1109\/FOCS.2010.67"},{"key":"1_CR1212","doi-asserted-by":"crossref","unstructured":"Venkataraman G, Sahni S, Mukhopadhyaya S (2003) A blocked all-pairs shortest paths algorithm. J Exp Algorithms 8","DOI":"10.1145\/996546.996553"},{"key":"1_CR1213","doi-asserted-by":"crossref","unstructured":"Williams R (2014) Faster all-pairs shortest paths via circuit complexity. In Proceedings of the 46th ACM symposium on theory of computing (STOC), New York, pp\u00a0664\u2013673","DOI":"10.1145\/2591796.2591811"},{"key":"1_CR1214","doi-asserted-by":"crossref","unstructured":"Zwick U (2001) Exact and approximate distances in graphs \u2013 a survey. In: Proceedings of the 9th European symposium on algorithms (ESA), Aarhus, pp\u00a033\u201348. See updated version at http:\/\/www.cs.tau.ac.il\/~zwick\/","DOI":"10.1007\/3-540-44676-1_3"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,6]],"date-time":"2019-09-06T19:06:34Z","timestamp":1567796794000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_11","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}