{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:32:34Z","timestamp":1766136754000,"version":"3.45.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,8,3]],"date-time":"2017-08-03T00:00:00Z","timestamp":1501718400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001732","name":"Danish National Research Foundation","doi-asserted-by":"crossref","award":["DNRF84"],"award-info":[{"award-number":["DNRF84"]}],"id":[{"id":"10.13039\/501100001732","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1217338, CNS-1318294 and CCF-1514383"],"award-info":[{"award-number":["CCF-1217338, CNS-1318294 and CCF-1514383"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Center for Massive Algorithms"},{"name":"Binational Science Foundation","award":["2008390"],"award-info":[{"award-number":["2008390"]}]},{"name":"Lynn and William Frankel Center for Computer Science"},{"name":"Israeli Academy of Science","award":["593\/11 and 724\/15"],"award-info":[{"award-number":["593\/11 and 724\/15"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,9,2]]},"abstract":"\n Thorup and Zwick [2001a] proposed a landmark distance oracle with the following properties. Given an\n n<\/jats:italic>\n -vertex undirected graph\n G<\/jats:italic>\n = (\n V<\/jats:italic>\n ,\n E<\/jats:italic>\n ) and a parameter\n k<\/jats:italic>\n = 1, 2, \u2026, their oracle has size\n O<\/jats:italic>\n (\n kn<\/jats:italic>\n \n 1 + 1\/\n k<\/jats:italic>\n <\/jats:sup>\n ), and upon a query (\n u<\/jats:italic>\n ,\n v<\/jats:italic>\n ) it constructs a path \u03a0 between\n u<\/jats:italic>\n and\n v<\/jats:italic>\n of length \u03b4(\n u<\/jats:italic>\n ,\n v<\/jats:italic>\n ) such that\n \n d\n G<\/jats:sub>\n <\/jats:italic>\n (\n u<\/jats:italic>\n ,\n v<\/jats:italic>\n ) \u2a7d \u03b4(\n u<\/jats:italic>\n ,\n v<\/jats:italic>\n ) \u2a7d (2\n k<\/jats:italic>\n \u2212 1)\n \n d\n G<\/jats:sub>\n <\/jats:italic>\n (\n u<\/jats:italic>\n ,\n v<\/jats:italic>\n ). The query time of the oracle from Thorup and Zwick [2001a] is\n O<\/jats:italic>\n (\n k<\/jats:italic>\n ) (in addition to the length of the returned path), and it was subsequently improved to\n O<\/jats:italic>\n (1) [Wulff-Nilsen 2012; Chechik 2014]. A major drawback of the oracle of Thorup and Zwick [2001a] is that its space is \u03a9(\n n<\/jats:italic>\n \u00b7 log\n n<\/jats:italic>\n ). Mendel and Naor [2006] devised an oracle with space\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \n 1 + 1\/\n k<\/jats:italic>\n <\/jats:sup>\n ) and stretch\n O<\/jats:italic>\n (\n k<\/jats:italic>\n ), but their oracle can only report distance estimates and not actual paths. In this article, we devise a path-reporting distance oracle with size\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \n 1 + 1\/\n k<\/jats:italic>\n <\/jats:sup>\n ), stretch\n O<\/jats:italic>\n (\n k<\/jats:italic>\n ), and query time\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \u03f5<\/jats:sup>\n ), for an arbitrarily small constant \u03f5 > 0. In particular, for\n k<\/jats:italic>\n = log\n n<\/jats:italic>\n , our oracle provides logarithmic stretch using linear size. Another variant of our oracle has size\n O<\/jats:italic>\n (\n n<\/jats:italic>\n loglog\n n<\/jats:italic>\n ), polylogarithmic stretch, and query time\n O<\/jats:italic>\n (loglog\n n<\/jats:italic>\n ).\n <\/jats:p>\n \n For unweighted graphs, we devise a distance oracle with multiplicative stretch\n O<\/jats:italic>\n (1), additive stretch\n O<\/jats:italic>\n (\u03b2(\n k<\/jats:italic>\n )), for a function \u03b2(\u00b7), space\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \n 1 + 1\/\n k<\/jats:italic>\n <\/jats:sup>\n ), and query time\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \u03f5<\/jats:sup>\n ), for an arbitrarily small constant \u03f5 > 0. The tradeoff between multiplicative stretch and size in these oracles is far below Erd\u0151s\u2019s girth conjecture threshold (which is stretch 2\n k<\/jats:italic>\n \u2212 1 and size\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \n 1 + 1\/\n k<\/jats:italic>\n <\/jats:sup>\n )). Breaking the girth conjecture tradeoff is achieved by exhibiting a tradeoff of different nature between additive stretch \u03b2(\n k<\/jats:italic>\n ) and size\n O<\/jats:italic>\n (\n n<\/jats:italic>\n \n 1 + 1\/\n k<\/jats:italic>\n <\/jats:sup>\n ). A similar type of tradeoff was exhibited by a construction of (1 + \u03f5, \u03b2)-spanners due to Elkin and Peleg [2001]. However, so far (1 + \u03f5, \u03b2)-spanners had no counterpart in the distance oracles\u2019 world.\n <\/jats:p>\n An important novel tool that we develop on the way to these results is a distance-preserving path-reporting oracle. We believe that this oracle is of independent interest.<\/jats:p>","DOI":"10.1145\/2888397","type":"journal-article","created":{"date-parts":[[2016,8,4]],"date-time":"2016-08-04T09:26:34Z","timestamp":1470302794000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs"],"prefix":"10.1145","volume":"12","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,8,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Ittai Abraham and Cyril Gavoille. 2011. On approximate distance labels and routing schemes with affine stretch. In DISC. 404--415.","DOI":"10.5555\/2075029.2075081"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148143"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","unstructured":"Ittai Abraham and Ofer Neiman. 2012. Using petal-decompositions to build a low stretch spanning tree. In STOC. 395--406. 10.1145\/2213977.2214015","DOI":"10.1145\/2213977.2214015"},{"key":"e_1_2_1_4_1","unstructured":"R. Agarwal. 2014a. Personal communication. (2014)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_5"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.38"},{"key":"e_1_2_1_7_1","volume-title":"Philip Brighten Godfrey, and Sariel Har-Peled","author":"Agarwal Rachit","year":"2011","unstructured":"Rachit Agarwal, Philip Brighten Godfrey, and Sariel Har-Peled. 2011. Approximate distance queries and compact routing in sparse graphs. In INFOCOM. 1754--1762."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","unstructured":"Ingo Alth\u00f6fer Gautam Das David P. Dobkin and Deborah Joseph. 1990. Generating sparse spanners for weighted graphs. In SWAT. 26--37.","DOI":"10.5555\/645895.671782"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Yair Bartal. 1996. Probabilistic approximations of metric spaces and its algorithmic applications. In FOCS. 184--193.","DOI":"10.5555\/874062.875536"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Surender Baswana Akshay Gaur Sandeep Sen and Jayant Upadhyay. 2008. Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error. In ICALP (1). 609--621. 10.1007\/978-3-540-70575-8_50","DOI":"10.1007\/978-3-540-70575-8_50"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Surender Baswana and Telikepalli Kavitha. 2006. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In FOCS. 591--602. 10.1109\/FOCS.2006.29","DOI":"10.1109\/FOCS.2006.29"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198518"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1024185"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591801"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070524"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.383983"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Michael Elkin Yuval Emek Daniel A. Spielman and Shang-Hua Teng. 2005. Lower-stretch spanning trees. In STOC. 494--503. 10.1145\/1060590.1060665","DOI":"10.1145\/1060590.1060665"},{"key":"e_1_2_1_18_1","volume-title":"Space-efficient path-reporting distance oracles. CoRR abs\/1410.0768","author":"Elkin Michael","year":"2014","unstructured":"Michael Elkin, Ofer Neiman, and Christian Wulff-Nilsen. 2014. Space-efficient path-reporting distance oracles. CoRR abs\/1410.0768 (2014). http:\/\/arxiv.org\/abs\/1410.0768."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380797"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.55"},{"key":"e_1_2_1_21_1","unstructured":"S. Halperin and U. Zwick. 2000. Unpublished manuscript. (2000)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00058-L"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761110"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","unstructured":"Manor Mendel and Assaf Naor. 2006. Ramsey partitions and proximity data structures. In FOCS. 109--118. 10.1109\/FOCS.2006.65","DOI":"10.1109\/FOCS.2006.65"},{"key":"e_1_2_1_26_1","volume-title":"Invited Talk and Paper in Advances in Data Structures (Preconference Workshop of FSTTCS).","author":"Milterson Peter Bro","year":"1999","unstructured":"Peter Bro Milterson. 1999. Cell probe complexity - A survey. In Invited Talk and Paper in Advances in Data Structures (Preconference Workshop of FSTTCS)."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","unstructured":"Mihai P\u01cetra\u015fcu and Liam Roditty. 2010. Distance oracles beyond the Thorup-Zwick bound. In FOCS. 815--823. 10.1109\/FOCS.2010.83","DOI":"10.1109\/FOCS.2010.83"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","unstructured":"Mihai P\u01cetra\u015fcu Liam Roditty and Mikkel Thorup. 2012. A new infinity of distance oracles for sparse graphs. In FOCS. 738--747. 10.1109\/FOCS.2012.44","DOI":"10.1109\/FOCS.2012.44"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65953"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644022"},{"key":"e_1_2_1_33_1","volume-title":"set, query&excl","author":"Porat Ely","year":"2013","unstructured":"Ely Porat and Liam Roditty. 2013. Preprocess, set, query! Algorithmica 67, 4 (2013), 516--528."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27848-8_571-1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","unstructured":"Liam Roditty Mikkel Thorup and Uri Zwick. 2005. Deterministic constructions of approximate distance oracles and spanners. In ICALP. 261--272. 10.1007\/11523468_22","DOI":"10.1007\/11523468_22"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","unstructured":"Christian Sommer Elad Verbin and Wei Yu. 2009. Distance oracles for sparse graphs. In FOCS. 703--712. 10.1109\/FOCS.2009.27","DOI":"10.1109\/FOCS.2009.27"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380798"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378581"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109645"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","unstructured":"Christian Wulff-Nilsen. 2012. Approximate distance oracles with improved preprocessing time. In SODA. 202--208.","DOI":"10.5555\/2095116.2095134"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2888397","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2888397","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2888397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:27:08Z","timestamp":1763458028000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2888397"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,3]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,9,2]]}},"alternative-id":["10.1145\/2888397"],"URL":"https:\/\/doi.org\/10.1145\/2888397","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2016,8,3]]},"assertion":[{"value":"2015-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}