{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:20:20Z","timestamp":1762917620159,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662480533"},{"type":"electronic","value":"9783662480540"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48054-0_6","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T11:57:29Z","timestamp":1439207849000},"page":"62-74","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On the Complexity of Hub Labeling (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Maxim","family":"Babenko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew V.","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruslan","family":"Savchenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"key":"6_CR1","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension and provably efficient shortest path algorithms. TR MSR-TR-2013-91, Microsoft Research (2013)"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/978-3-642-22006-7_58","volume-title":"Automata, Languages and Programming","author":"I Abraham","year":"2011","unstructured":"Abraham, I., Delling, D., Fiat, A., Goldberg, A.V., Werneck, R.F.: VC-dimension and shortest path algorithms. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 690\u2013699. Springer, Heidelberg (2011)"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/978-3-642-20662-7_20","volume-title":"Experimental Algorithms","author":"I Abraham","year":"2011","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: A hub-based labeling algorithm for shortest paths in road networks. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 230\u2013241. Springer, Heidelberg (2011)"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-33090-2_4","volume-title":"Algorithms \u2013 ESA 2012","author":"I Abraham","year":"2012","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 24\u201335. Springer, Heidelberg (2012)"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms, pp. 782\u2013793 (2010)","DOI":"10.1137\/1.9781611973075.64"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Yoshida, Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: SIGMOD 2013, pp. 349\u2013360. ACM, New York (2013)","DOI":"10.1145\/2463676.2465315"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/978-3-642-39206-1_7","volume-title":"Automata, Languages, and Programming","author":"M Babenko","year":"2013","unstructured":"Babenko, M., Goldberg, A.V., Gupta, A., Nagarajan, V.: Algorithms for hub label optimization. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 69\u201380. Springer, Heidelberg (2013)"},{"key":"6_CR8","unstructured":"Babenko, M., Goldberg, A.V., Kaplan, H., Savchenko, R., Weller, M.: On the Complexity of Hub Labeling (2015). http:\/\/arxiv.org\/abs\/1501.02492 [cs.DS]"},{"issue":"5","key":"6_CR9","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338\u20131355 (2003)","journal-title":"SIAM J. Comput."},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Delling, D., Goldberg, A.V., Pajor, T., Werneck, R.F.: Robust exact distance queries on massive networks. TR MSR-TR-2014-12, Microsoft Research (2014)","DOI":"10.1007\/978-3-662-44777-2_27"},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/978-3-319-07959-2_22","volume-title":"Experimental Algorithms","author":"D Delling","year":"2014","unstructured":"Delling, D., Goldberg, A.V., Savchenko, R., Werneck, R.F.: Hub labels: theory and practice. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 259\u2013270. Springer, Heidelberg (2014)"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G Gallo","year":"1989","unstructured":"Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18, 30\u201355 (1989)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"6_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/978-3-642-40313-2_42","volume-title":"Mathematical Foundations of Computer Science 2013","author":"AV Goldberg","year":"2013","unstructured":"Goldberg, A.V., Razenshteyn, I., Savchenko, R.: Separating hierarchical and general hub labelings. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 469\u2013479. Springer, Heidelberg (2013)"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1006\/jagm.1994.1032","volume":"17","author":"G Kortsarz","year":"1994","unstructured":"Kortsarz, G., Peleg, D.: Generating sparse 2-spanners. J. Alg. 17, 222\u2013236 (1994)","journal-title":"J. Alg."},{"issue":"3","key":"6_CR16","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5","volume":"33","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Proximity-preserving labeling schemes. J. Gr. Th. 33(3), 167\u2013176 (2000)","journal-title":"J. Gr. Th."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48054-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T13:39:21Z","timestamp":1674567561000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48054-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480533","9783662480540"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48054-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"11 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}