{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T04:11:08Z","timestamp":1746072668091,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642382352"},{"type":"electronic","value":"9783642382369"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38236-9_5","type":"book-chapter","created":{"date-parts":[[2013,4,15]],"date-time":"2013-04-15T02:38:02Z","timestamp":1365993482000},"page":"42-51","source":"Crossref","is-referenced-by-count":5,"title":["(1\u2009+\u2009\u03b5)-Distance Oracles for Vertex-Labeled Planar Graphs"],"prefix":"10.1007","author":[{"given":"Mingfei","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chu Chung Christopher","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Li","family":"Ning","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Gottlieb, L.-A., Kopelowitz, T., Lewenstein, M., Roditty, L.: Fast, precise and dynamic distance queries. In: SODA, pp. 840\u2013853 (2011)","DOI":"10.1137\/1.9781611973082.66"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Chechik, S.: Improved distance oracles for vertex-labeled graphs. CoRR, abs\/1109.3114 (2011)","DOI":"10.1007\/978-3-642-33090-2_29"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A.: Searching dynamic point sets in spaces with bounded doubling dimension. In: STOC, pp. 574\u2013583 (2006)","DOI":"10.1145\/1132516.1132599"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/978-3-540-74450-4_41","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"J. Fischer","year":"2007","unstructured":"Fischer, J., Heun, V.: A new succinct representation of rmq-information and improvements in the enhanced suffix array. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol.\u00a04614, pp. 459\u2013470. Springer, Heidelberg (2007)"},{"key":"5_CR5","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":"5_CR6","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.i., Klein, P.N., Sommer, C.: Linear-space approximate distance oracles for planar, bounded-genus, and minor-free graphs. CoRR, abs\/1104.5214 (2011)","DOI":"10.1007\/978-3-642-22006-7_12"},{"key":"5_CR7","first-page":"820","volume-title":"Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002","author":"P. Klein","year":"2002","unstructured":"Klein, P.: Preprocessing an undirected planar network to enable fast approximate distance queries. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, pp. 820\u2013827. Society for Industrial and Applied Mathematics, Philadelphia (2002)"},{"key":"5_CR8","first-page":"162","volume-title":"Proceedings of the 18th Annual Symposium on Foundations of Computer Science","author":"R.J. Lipton","year":"1977","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pp. 162\u2013170. IEEE Computer Society, Washington, DC (1977)"},{"issue":"2","key":"5_CR9","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 on Applied Mathematics\u00a036(2), 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Mozes, S., Sommer, C.: Exact distance oracles for planar graphs. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 209\u2013222. SIAM (2012)","DOI":"10.1137\/1.9781611973099.19"},{"key":"5_CR11","unstructured":"Sommer, C.: More compact oracles for approximate distances in planar graphs. CoRR, abs\/1109.2641 (2011)"},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1145\/1989323.1989385","volume-title":"Proceedings of the 2011 International Conference on Management of Data, SIGMOD 2011","author":"Y. Tao","year":"2011","unstructured":"Tao, Y., Papadopoulos, S., Sheng, C., Stefanidis, K.: Nearest keyword search in xml documents. In: Proceedings of the 2011 International Conference on Management of Data, SIGMOD 2011, pp. 589\u2013600. ACM, New York (2011)"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1109\/SFCS.1997.646088","volume-title":"Proceedings of the 38th Annual Symposium on Foundations of Computer Science","author":"M. Thorup","year":"1997","unstructured":"Thorup, M.: Undirected single source shortest paths in linear time. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p. 12. IEEE Computer Society, Washington, DC (1997)"},{"key":"5_CR14","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM\u00a051, 993\u20131024 (2004)","journal-title":"J. ACM"},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/380752.380798","volume-title":"Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC 2001","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC 2001, pp. 183\u2013192. ACM, New York (2001)"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Wulff-Nilsen, C.: Approximate distance oracles with improved preprocessing time. In: SODA 2012 (2012)","DOI":"10.1137\/1.9781611973099.18"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38236-9_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T04:40:58Z","timestamp":1745988058000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-38236-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642382352","9783642382369"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38236-9_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}