{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:26:43Z","timestamp":1725496003135},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770497"},{"type":"electronic","value":"9783540770503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-77050-3_27","type":"book-chapter","created":{"date-parts":[[2007,11,26]],"date-time":"2007-11-26T08:39:22Z","timestamp":1196066362000},"page":"328-339","source":"Crossref","is-referenced-by-count":2,"title":["Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs"],"prefix":"10.1007","author":[{"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","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 Journal on Computing\u00a028, 1167\u20131181 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR2","doi-asserted-by":"publisher","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 Journal on Computing\u00a028, 263\u2013277 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Baswana, S., Goyal, V., Sen, S.: All-pairs nearly 2-approximate shortest paths in O(n 2 polylog n) time. In: 22nd Annual Symposium on Theoretical Aspect of Computer Science, pp. 666\u2013679 (2005)","DOI":"10.1007\/978-3-540-31856-9_55"},{"key":"27_CR4","doi-asserted-by":"crossref","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)","DOI":"10.1109\/FOCS.2006.29"},{"key":"27_CR5","doi-asserted-by":"crossref","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)","DOI":"10.1145\/1250790.1250877"},{"key":"27_CR6","doi-asserted-by":"publisher","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 t. SIAM Journal on Computing\u00a028, 210\u2013236 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"27_CR7","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":"27_CR8","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":"27_CR9","first-page":"282","volume":"1","author":"M. Elkin","year":"2005","unstructured":"Elkin, M.: Computing almost shortest paths. ACM Transactions on Algorithms (TALG)\u00a01, 282\u2013323 (2005)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"27_CR10","doi-asserted-by":"publisher","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. Journal of Complexity\u00a014, 257\u2013299 (1998)","journal-title":"Journal of Complexity"},{"key":"27_CR11","unstructured":"K avitha, T.: Faster Algorithms for All-Pairs Small Stretch Distances in Weighted Graphs (Full version), http:\/\/drona.csa.iisc.ernet.in\/~kavitha\/fst07.pdf"},{"key":"27_CR12","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":"27_CR13","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":"27_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. Journal of Association of Computing Machinery\u00a052, 1\u201324 (2005)","journal-title":"Journal of Association of Computing Machinery"},{"key":"27_CR15","doi-asserted-by":"publisher","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. Journal of Association of Computing Machinery\u00a049, 289\u2013317 (2002)","journal-title":"Journal of Association of Computing Machinery"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77050-3_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:55:54Z","timestamp":1619520954000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77050-3_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540770497","9783540770503"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77050-3_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}