{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:46:59Z","timestamp":1756000019567},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540249986"},{"type":"electronic","value":"9783540318569"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_55","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T18:06:19Z","timestamp":1267553179000},"page":"666-679","source":"Crossref","is-referenced-by-count":11,"title":["All-Pairs Nearly 2-Approximate Shortest-Paths in O(n 2 polylog n) Time"],"prefix":"10.1007","author":[{"given":"Surender","family":"Baswana","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vishrut","family":"Goyal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sandeep","family":"Sen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"55_CR1","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in \u00d5(n2) time. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 271\u2013280 (2004)"},{"key":"55_CR2","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.2000.1117","volume":"38","author":"E. Cohen","year":"2001","unstructured":"Cohen, E., Zwick, U.: All-pairs small stretch paths. Journal of Algorithms\u00a038, 335\u2013353 (2001)","journal-title":"Journal of Algorithms"},{"key":"55_CR3","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D. Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All pairs almost shortest paths. Siam Journal on Computing\u00a029, 1740\u20131759 (2000)","journal-title":"Siam Journal on Computing"},{"key":"55_CR4","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Computing almost shortest paths. In: Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing, pp. 53\u201362 (2001)","DOI":"10.1145\/383962.383983"},{"key":"55_CR5","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with o(1) worst case time. Journal of ACM\u00a031, 538\u2013544 (1984)","journal-title":"Journal of ACM"},{"key":"55_CR6","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 new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science\u00a0312, 47\u201374 (2004)","journal-title":"Theoretical Computer Science"},{"key":"55_CR7","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracle. In: Proceedings of 33rd ACM Symposium on Theory of Computing (STOC), pp. 183\u2013192 (2001)","DOI":"10.1145\/380752.380798"},{"key":"55_CR8","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: 13th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"key":"55_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/3-540-44676-1_3","volume-title":"Algorithms - ESA 2001","author":"U. Zwick","year":"2001","unstructured":"Zwick, U.: Exact and approximate distances in graphs - a survey. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 33\u201348. Springer, Heidelberg (2001)"},{"key":"55_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1007\/978-3-540-30551-4_78","volume-title":"Algorithms and Computation","author":"U. Zwick","year":"2004","unstructured":"Zwick, U.: Slightly improved sub-cubic bound for computing all-pairs shortest paths. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 921\u2013932. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","STACS 2005"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T17:30:08Z","timestamp":1558287008000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}