{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T18:12:21Z","timestamp":1648577541336},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,6,1]],"date-time":"2011-06-01T00:00:00Z","timestamp":1306886400000},"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":[[2012,6]]},"DOI":"10.1007\/s00453-011-9529-y","type":"journal-article","created":{"date-parts":[[2011,5,31]],"date-time":"2011-05-31T11:34:13Z","timestamp":1306841653000},"page":"224-245","source":"Crossref","is-referenced-by-count":0,"title":["Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs"],"prefix":"10.1007","volume":"63","author":[{"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,6,1]]},"reference":[{"key":"9529_CR1","doi-asserted-by":"crossref","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D. Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28, 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"key":"9529_CR2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1137\/S0097539794271898","volume":"28","author":"B. Awerbuch","year":"1998","unstructured":"Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Near-linear time construction of sparse neighborhood covers. SIAM J. Comput. 28, 263\u2013277 (1998)","journal-title":"SIAM J. Comput."},{"key":"9529_CR3","first-page":"666","volume-title":"22nd Annual Symposium on Theoretical Aspect of Computer Science","author":"S. Baswana","year":"2005","unstructured":"Baswana, S., Goyal, V., Sen, S.: All-pairs nearly 2-approximate shortest paths in O(n 2\u00a0polylog\u00a0n) time. In: 22nd Annual Symposium on Theoretical Aspect of Computer Science, pp. 666\u2013679 (2005)"},{"key":"9529_CR4","first-page":"591","volume-title":"47th IEEE Symposium on Foundations of Computer Science","author":"S. Baswana","year":"2006","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: 47th IEEE Symposium on Foundations of Computer Science, pp. 591\u2013602 (2006)"},{"key":"9529_CR5","first-page":"590","volume-title":"Proceedings of 39th Annual ACM Symposium on Theory of Computing (STOC)","author":"T. Chan","year":"2007","unstructured":"Chan, T.: More algorithms for all-pairs shortest paths in weighted graphs. In: Proceedings of 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 590\u2013598 (2007)"},{"key":"9529_CR6","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/S0097539794261295","volume":"28","author":"E. Cohen","year":"1998","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch\u00a0t. SIAM J. Comput. 28, 210\u2013236 (1998)","journal-title":"SIAM J. Comput."},{"key":"9529_CR7","doi-asserted-by":"crossref","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. J. Algorithms 38, 335\u2013353 (2001)","journal-title":"J. Algorithms"},{"key":"9529_CR8","doi-asserted-by":"crossref","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 J. Comput. 29, 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"key":"9529_CR9","first-page":"282","volume":"1","author":"M. Elkin","year":"2005","unstructured":"Elkin, M.: Computing almost shortest paths. ACM Trans. Algorithms (TALG) 1, 282\u2013323 (2005)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"9529_CR10","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 multiplication and applications. J. Complex. 14, 257\u2013299 (1998)","journal-title":"J. Complex."},{"key":"9529_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"key":"9529_CR12","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 312, 47\u201374 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9529_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. Assoc. Comput. Mach. 52, 1\u201324 (2005)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9529_CR14","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1137\/1.9781611973068.103","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"R. Yuster","year":"2009","unstructured":"Yuster, R.: Efficient algorithms on sets of permutations, dominance, and real-weighted APSP. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 950\u2013957 (2009)"},{"key":"9529_CR15","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. Assoc. Comput. Mach. 49, 289\u2013317 (2002)","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9529-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9529-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9529-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:07Z","timestamp":1559123107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9529-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,1]]},"references-count":15,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9529"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9529-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,1]]}}}