{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:43:43Z","timestamp":1725489823725},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540739487"},{"type":"electronic","value":"9783540739517"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73951-7_47","type":"book-chapter","created":{"date-parts":[[2007,8,20]],"date-time":"2007-08-20T10:18:03Z","timestamp":1187605083000},"page":"541-552","source":"Crossref","is-referenced-by-count":8,"title":["Faster Approximation of Distances in Graphs"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Berman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiva Prasad","family":"Kasiviswanathan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"47_CR1","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. In: STOC 2007, ACM (to appear)","DOI":"10.1145\/1250790.1250877"},{"issue":"2","key":"47_CR2","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1006\/inco.1997.2620","volume":"134","author":"Z. Galil","year":"1997","unstructured":"Galil, Z., Margalit, O.: All pairs shortest distances for graphs with small integer length edges. Information and Computation\u00a0134(2), 103\u2013139 (1997)","journal-title":"Information and Computation"},{"issue":"2","key":"47_CR3","first-page":"243","volume":"54","author":"Z. Galil","year":"1997","unstructured":"Galil, Z., Margalit, O.: All pairs shortest paths for graphs with small integer length edges. JCSS\u00a054(2), 243\u2013254 (1997)","journal-title":"JCSS"},{"key":"47_CR4","doi-asserted-by":"crossref","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. JCSS 51 (1995)","DOI":"10.1006\/jcss.1995.1078"},{"key":"47_CR5","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetical progressions. Journal of Symbolic Computation\u00a09, 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"47_CR6","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)"},{"issue":"4","key":"47_CR7","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(4), 1167\u20131181 (1999)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"47_CR8","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(2), 335\u2013353 (2001)","journal-title":"Journal of Algorithms"},{"issue":"5","key":"47_CR9","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(5), 1740\u20131759 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"47_CR10","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: FOCS 2006, IEEE, pp. 591\u2013602 (2006)","DOI":"10.1109\/FOCS.2006.29"},{"issue":"2","key":"47_CR11","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1145\/1103963.1103968","volume":"1","author":"M. Elkin","year":"2005","unstructured":"Elkin, M.: Computing almost shortest paths. ACM Transactions on Algorithms\u00a01(2), 283\u2013323 (2005)","journal-title":"ACM Transactions on Algorithms"},{"key":"47_CR12","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. In: SODA 2006, ACM, pp. 514\u2013523 (2006)","DOI":"10.1145\/1109557.1109614"},{"key":"47_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/11764298_9","volume-title":"Experimental Algorithms","author":"K. Boitmanis","year":"2006","unstructured":"Boitmanis, K., Freivalds, K., Ledins, P., Opmanis, R.: Fast and simple approximation of the diameter and radius of a graph. In: \u00c0lvarez, C., Serna, M. (eds.) WEA 2006. LNCS, vol.\u00a04007, pp. 98\u2013108. Springer, Heidelberg (2006)"},{"key":"47_CR14","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications 3(3) (1999)","DOI":"10.7155\/jgaa.00014"},{"key":"47_CR15","unstructured":"Berman, P., Kasiviswanathan, S.P.: Faster approximation of distances in graphs (2007), Available at http:\/\/www.cse.psu.edu\/~kasivisw\/fadig.pdf"},{"issue":"1","key":"47_CR16","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 ACM\u00a052(1), 1\u201324 (2005)","journal-title":"Journal of ACM"},{"key":"47_CR17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal of Applied Mathematics\u00a036, 177\u2013189 (1979)","journal-title":"SIAM Journal of Applied Mathematics"},{"issue":"1","key":"47_CR18","first-page":"3","volume":"55","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. JCSS\u00a055(1), 3\u201323 (1997)","journal-title":"JCSS"},{"issue":"1","key":"47_CR19","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1006\/jcom.1997.0438","volume":"13","author":"D. Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Rectangular matrix multiplication revisited. Journal of Complexity\u00a013(1), 42\u201349 (1997)","journal-title":"Journal of Complexity"},{"issue":"2","key":"47_CR20","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(2), 257\u2013299 (1998)","journal-title":"Journal of Complexity"},{"issue":"2","key":"47_CR21","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1006\/jagm.1996.0048","volume":"21","author":"E. Cohen","year":"1996","unstructured":"Cohen, E.: Efficient parallel shortest-paths in digraphs with a separator decomposition. Journal of Algorithms\u00a021(2), 331\u2013357 (1996)","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73951-7_47.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:06:01Z","timestamp":1619517961000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73951-7_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540739487","9783540739517"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73951-7_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}