{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T16:09:28Z","timestamp":1775578168248,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,2,12]],"date-time":"2016-02-12T00:00:00Z","timestamp":1455235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","award":["2008348"],"award-info":[{"award-number":["2008348"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["894\/09"],"award-info":[{"award-number":["894\/09"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Israel Ministry of Science and Technology"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,12]]},"abstract":"<jats:p>\n            This article proposes a forbidden-set labeling scheme for the family of unweighted graphs with doubling dimension bounded by \u03b1. For an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph\n            <jats:italic>G<\/jats:italic>\n            in this family, and for any desired precision parameter \u03f5 &gt; 0, the labeling scheme stores an\n            <jats:italic>O<\/jats:italic>\n            (1 + \u03f5\n            <jats:sup>\u2212 1<\/jats:sup>\n            )\n            <jats:sup>2\u03b1<\/jats:sup>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            -bit label at each vertex. Given the labels of two end-vertices\n            <jats:italic>s<\/jats:italic>\n            and\n            <jats:italic>t<\/jats:italic>\n            , and the labels of a set\n            <jats:italic>F<\/jats:italic>\n            of \u201cforbidden\u201d vertices and\/or edges, our scheme can compute, in\n            <jats:italic>O<\/jats:italic>\n            (1 + \u03f5\n            <jats:sup>\u2212 1<\/jats:sup>\n            )\n            <jats:sup>2\u03b1<\/jats:sup>\n            \u00b7 |\n            <jats:italic>F<\/jats:italic>\n            |\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            time, a 1 + \u03f5 stretch approximation for the distance between\n            <jats:italic>s<\/jats:italic>\n            and\n            <jats:italic>t<\/jats:italic>\n            in the graph\n            <jats:italic>G<\/jats:italic>\n            \u2216\n            <jats:italic>F<\/jats:italic>\n            . The labeling scheme can be extended into a forbidden-set labeled routing scheme with stretch 1 + \u03f5 for graphs of bounded doubling dimension.\n          <\/jats:p>","DOI":"10.1145\/2818694","type":"journal-article","created":{"date-parts":[[2016,2,22]],"date-time":"2016-02-22T13:07:16Z","timestamp":1456146436000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension"],"prefix":"10.1145","volume":"12","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[{"name":"VMware Research, Palo Alto, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiri","family":"Chechik","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Bordeaux, LaBRI, IUF, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[{"name":"The Weizmann Institute of Science, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,2,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214084"},{"key":"e_1_2_1_2_1","volume-title":"10th International Conference on Experimental Algorithms (SEA). 230--241","author":"Abraham Ittai","unstructured":"Ittai Abraham , Daniel Delling , Andrew V. Goldberg , and Renato F. Werneck . 2011. A Hub-based labeling algorithm for shortest paths in road networks . In 10th International Conference on Experimental Algorithms (SEA). 230--241 . Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2011. A Hub-based labeling algorithm for shortest paths in road networks. In 10th International Conference on Experimental Algorithms (SEA). 230--241."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_22"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873665"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146411"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2006.72"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536431"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2008.06.030"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027223.2027232"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484268"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888935.1888946"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1763424.1763430"},{"key":"e_1_2_1_13_1","first-page":"187","article-title":"Compact routing. In Algorithms for Sensor and Ad Hoc Networks","volume":"4621","author":"Dom Michael","year":"2007","unstructured":"Michael Dom . 2007 . Compact routing. In Algorithms for Sensor and Ad Hoc Networks , LNCS 4621. 187 -- 202 . Michael Dom. 2007. Compact routing. In Algorithms for Sensor and Ad Hoc Networks, LNCS 4621. 187--202.","journal-title":"LNCS"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496826"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 13th Symposium on Discrete Algorithms (SODA). 838--843","author":"Demetrescu Camil","year":"2002","unstructured":"Camil Demetrescu and Mikkel Thorup . 2002 . Oracles for distances avoiding a link-failure . In Proceedings of the 13th Symposium on Discrete Algorithms (SODA). 838--843 . Camil Demetrescu and Mikkel Thorup. 2002. Oracles for distances avoiding a link-failure. In Proceedings of the 13th Symposium on Discrete Algorithms (SODA). 838--843."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2008.163"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS), 534--543","author":"Gupta Anupam","unstructured":"Anupam Gupta , Robert Krauthgamer , and James R. Lee . 2003. Bounded geometries, fractals, and low-distortion embeddings . In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS), 534--543 , IEEE. Anupam Gupta, Robert Krauthgamer, and James R. Lee. 2003. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS), 534--543, IEEE."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0073-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 26th Symposium on Theoretical Aspects of Computer Science (STACS).","author":"Khanna Neelesh","year":"2010","unstructured":"Neelesh Khanna and Surender Baswana . 2010 . Approximate shortest path oracle under vertex failure . In Proceedings of the 26th Symposium on Theoretical Aspects of Computer Science (STACS). Neelesh Khanna and Surender Baswana. 2010. Approximate shortest path oracle under vertex failure. In Proceedings of the 26th Symposium on Theoretical Aspects of Computer Science (STACS)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273445.1273450"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2004.1354495"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 18th Symposium on Discrete Algorithms (SODA). 939--948","author":"Konjevod Goran","year":"2007","unstructured":"Goran Konjevod , Andr\u00e9a Werneck Richa , and Donglin Xia . 2007 . Optimal scale-free compact routing schemes in doubling networks . In Proceedings of the 18th Symposium on Discrete Algorithms (SODA). 939--948 . Goran Konjevod, Andr\u00e9a Werneck Richa, and Donglin Xia. 2007. Optimal scale-free compact routing schemes in doubling networks. In Proceedings of the 18th Symposium on Discrete Algorithms (SODA). 939--948."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_26"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/647680.732175"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/258492.258523"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.54"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073823"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/3271139.3271275"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_2_1_33_1","unstructured":"David Andrew Twigg. 2006. Forbidden-set Routing. PhD thesis University of Cambridge (King\u2019s College).  David Andrew Twigg. 2006. Forbidden-set Routing. PhD thesis University of Cambridge (King\u2019s College)."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818694","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818694","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:42:49Z","timestamp":1750225369000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818694"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,12]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,12]]}},"alternative-id":["10.1145\/2818694"],"URL":"https:\/\/doi.org\/10.1145\/2818694","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,12]]},"assertion":[{"value":"2014-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}