{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T16:08:27Z","timestamp":1775578107927,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642330896","type":"print"},{"value":"9783642330902","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_29","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T11:29:11Z","timestamp":1346153351000},"page":"325-336","source":"Crossref","is-referenced-by-count":7,"title":["Improved Distance Oracles and Spanners for Vertex-Labeled Graphs"],"prefix":"10.1007","author":[{"given":"Shiri","family":"Chechik","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/978-3-642-24100-0_39","volume-title":"Distributed Computing","author":"I. Abraham","year":"2011","unstructured":"Abraham, I., Gavoille, C.: On Approximate Distance Labels and Routing Schemes with Affine Stretch. In: Peleg, D. (ed.) Distributed Computing. LNCS, vol.\u00a06950, pp. 404\u2013415. Springer, Heidelberg (2011)"},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"key":"29_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1007\/978-3-540-70575-8_50","volume-title":"Automata, Languages and Programming","author":"S. Baswana","year":"2008","unstructured":"Baswana, S., Gaur, A., Sen, S., Upadhyay, J.: Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 609\u2013621. Springer, Heidelberg (2008)"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: FOCS, pp. 591\u2013602 (2006)","DOI":"10.1109\/FOCS.2006.29"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in expected O(n\n                2) time. ACM Transactions on Algorithms, 557\u2013577 (2006)","DOI":"10.1145\/1198513.1198518"},{"key":"29_CR6","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Theory of Graphs and Its Applications, pp. 29\u201336 (1964)"},{"issue":"2","key":"29_CR7","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0166-218X(03)00259-2","volume":"137","author":"A.M. Farley","year":"2004","unstructured":"Farley, A.M., Proskurowski, A., Zappala, D., Windisch, K.: Spanners and message distribution in networks. Discrete Applied Mathematics\u00a0137(2), 159\u2013171 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"29_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-642-22012-8_39","volume-title":"Automata, Languages and Programming","author":"D. Hermelin","year":"2011","unstructured":"Hermelin, D., Levy, A., Weimann, O., Yuster, R.: Distance Oracles for Vertex-Labeled Graphs. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol.\u00a06756, pp. 490\u2013501. Springer, Heidelberg (2011)"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Mendel, M., Naor, A.: Ramsey partitions and proximity data structures. Journal of the European Mathematical Society, 253\u2013275 (2007)","DOI":"10.4171\/JEMS\/79"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Roditty, L.: Distance oracles beyond the thorup-zwick bound. In: FOCS, pp. 815\u2013823 (2010)","DOI":"10.1109\/FOCS.2010.83"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Peleg, D., Sch\u00e1ffer, A.A.: Graph spanners. J. Graph Theory, 99\u2013116 (1989)","DOI":"10.1002\/jgt.3190130114"},{"issue":"4","key":"29_CR12","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Computing\u00a018(4), 740\u2013747 (1989)","journal-title":"SIAM J. Computing"},{"issue":"3","key":"29_CR13","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM\u00a036(3), 510\u2013530 (1989)","journal-title":"J. ACM"},{"key":"29_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/11523468_22","volume-title":"Automata, Languages and Programming","author":"L. Roditty","year":"2005","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic Constructions of Approximate Distance Oracles and Spanners. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 261\u2013272. Springer, Heidelberg (2005)"},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"Sommer, C., Verbin, E., Yu, W.: Distance oracles for sparse graphs. In: FOCS, pp. 703\u2013712 (2009)","DOI":"10.1109\/FOCS.2009.27"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. Journal of the ACM, 1\u201324 (2005)","DOI":"10.1145\/1044731.1044732"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Ziljstra, E.: Design and implementation of an effcient priority queue. Mathematical Systems Theory\u00a010, 99\u2013127 (1977)","journal-title":"Mathematical Systems Theory"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T07:54:52Z","timestamp":1620114892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}